The Algebra of Contracts
Inigo Incer
EECS Department, University of California, Berkeley
Technical Report No. UCB/EECS-2022-99
May 13, 2022
http://www2.eecs.berkeley.edu/Pubs/TechRpts/2022/EECS-2022-99.pdf
Today systems industries face significant challenges to bring products to market. Companies struggle to integrate into complex designs a large number of subsystems designed by various manufacturers. The number of recent high-profile recalls afflicting the automotive and avionics industries is a testament to the difficulty of system design.
The theory of contracts has been proposed to address these issues. Assume-guarantee (AG) contracts are specifications for components in a system that state what is expected from the environment in which the component operates and what is required from the object under specification provided that the environment meets the assumptions of the contract. A contract can thus be expressed as a pair C = (A, G) of formal properties: the assumptions A made on the environment and the guarantees G required from the component. By asking a third-party to implement a formal specification given as a contract, a system integrator knows a priori that the resulting system will meet its specifications. Thus, contracts can serve as the technical counterpart of the legal bindings between parties in a supply chain.
As AG contracts are specifications for components, the theory must offer means of manipulating specifications corresponding to tasks carried out in system design. There were three operations known on contracts before the work presented in this thesis: composition, conjunction, and disjunction. Composition is the algebraic operation which enables compositional design. It gives us the specification of a system built by components that obey the specifications being composed. Conjunction allows for concurrent design of the same object. When different groups are in charge of designing or characterizing different aspects, or viewpoints, of the same design element, they will produce specifications corresponding to the various viewpoints of that object. The operation of conjunction allows us to generate one specification that summarizes these diverse specifications.
Over the course of the research that led to this thesis, we introduced the operation of merging, or strong merging, which gives the specification of an object consisting of multiple viewpoints when each viewpoint's guarantees is required to hold simultaneously. In addition, we obtained adjoint operations for all previously mentioned operations. For example, the adjoint of composition, called quotient, yields the most relaxed specification which can be composed with the specification of a partial implementation of the design in order to meet a top-level spec. As a result of the work presented here, today we know eight operations on AG contracts and their closed-form expressions.
AG contracts require that the assumptions and guarantees of the pair (A, G) be specified as what in formal methods are called trace properties. This type of properties can express many requirements, such as safety (i.e., bad things don't happen) and liveness (i.e., good things eventually happen), but there are many statements we would like to make over systems that these properties cannot express. For instance, it has been shown that several security attributes, such as non-interference and observational determinism, cannot be expressed as trace properties. To express them, we need hyperproperties.
In this context, we introduce in this thesis the concept of hypercontracts. Hypercontracts are a fully-developed AG theory which allows us to reason compositionally about systems using pairs (A, G) of arbitrary hyperproperties. This theory extends the reach of AG reasoning to all system attributes we know how to formalize. This includes all known properties used in security and in machine learning.
Advisors: Alberto L. Sangiovanni-Vincentelli
BibTeX citation:
@phdthesis{Incer:EECS-2022-99,
Author= {Incer, Inigo},
Title= {The Algebra of Contracts},
School= {EECS Department, University of California, Berkeley},
Year= {2022},
Month= {May},
Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2022/EECS-2022-99.html},
Number= {UCB/EECS-2022-99},
Abstract= {Today systems industries face significant challenges to bring products to market. Companies struggle to integrate into complex designs a large number of subsystems designed by various manufacturers. The number of recent high-profile recalls afflicting the automotive and avionics industries is a testament to the difficulty of system design.
The theory of contracts has been proposed to address these issues. Assume-guarantee (AG) contracts are specifications for components in a system that state what is expected from the environment in which the component operates and what is required from the object under specification provided that the environment meets the assumptions of the contract. A contract can thus be expressed as a pair C = (A, G) of formal properties: the assumptions A made on the environment and the guarantees G required from the component. By asking a third-party to implement a formal specification given as a contract, a system integrator knows a priori that the resulting system will meet its specifications. Thus, contracts can serve as the technical counterpart of the legal bindings between parties in a supply chain.
As AG contracts are specifications for components, the theory must offer means of manipulating specifications corresponding to tasks carried out in system design. There were three operations known on contracts before the work presented in this thesis: composition, conjunction, and disjunction. Composition is the algebraic operation which enables compositional design. It gives us the specification of a system built by components that obey the specifications being composed. Conjunction allows for concurrent design of the same object. When different groups are in charge of designing or characterizing different aspects, or viewpoints, of the same design element, they will produce specifications corresponding to the various viewpoints of that object. The operation of conjunction allows us to generate one specification that summarizes these diverse specifications.
Over the course of the research that led to this thesis, we introduced the operation of merging, or strong merging, which gives the specification of an object consisting of multiple viewpoints when each viewpoint's guarantees is required to hold simultaneously. In addition, we obtained adjoint operations for all previously mentioned operations. For example, the adjoint of composition, called quotient, yields the most relaxed specification which can be composed with the specification of a partial implementation of the design in order to meet a top-level spec. As a result of the work presented here, today we know eight operations on AG contracts and their closed-form expressions.
AG contracts require that the assumptions and guarantees of the pair (A, G) be specified as what in formal methods are called trace properties. This type of properties can express many requirements, such as safety (i.e., bad things don't happen) and liveness (i.e., good things eventually happen), but there are many statements we would like to make over systems that these properties cannot express. For instance, it has been shown that several security attributes, such as non-interference and observational determinism, cannot be expressed as trace properties. To express them, we need hyperproperties.
In this context, we introduce in this thesis the concept of hypercontracts. Hypercontracts are a fully-developed AG theory which allows us to reason compositionally about systems using pairs (A, G) of arbitrary hyperproperties. This theory extends the reach of AG reasoning to all system attributes we know how to formalize. This includes all known properties used in security and in machine learning.},
}
EndNote citation:
%0 Thesis %A Incer, Inigo %T The Algebra of Contracts %I EECS Department, University of California, Berkeley %D 2022 %8 May 13 %@ UCB/EECS-2022-99 %U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2022/EECS-2022-99.html %F Incer:EECS-2022-99