Project

General

Profile

Wiki » History » Version 21

Andrei Tatarnikov, 07/10/2013 05:50 PM

1 1 Andrei Tatarnikov
h1. Constraint Solver API
2
3 2 Andrei Tatarnikov
h2. Basic Concepts
4 1 Andrei Tatarnikov
5 2 Andrei Tatarnikov
Constraint Solver Java API provides a Java API for generating pseudorandom values that satisfy certain constraints. This feature is important for test generators that aim at creating directed tests. At logical level, a constraint is represented by a set of expressions that specify limitations for input values (assertions that must be hold for those values). If there are values satisfying all of the specified assertions they will be used a solution for the constraint. If there is a multitude of values satisfying the constraint, specific values will be selected from the range of possible solutions on random basis.
6
7 4 Andrei Tatarnikov
From an implementational point of view, the API represents a wrapper around some kind of an openly distributed SMT solver engine (in the current version, we use the Z3 solver by Microsoft Research). It can be extended to support other solver engines and it provides a possibility to interact with different solver engines in a uniform way. Also, it facilitates creating task-specific custom solvers and extending functionality of existing solver engines by adding custom operations (macros based on built-in operations).
8 2 Andrei Tatarnikov
9 3 Andrei Tatarnikov
h2. SMT-LIB
10 2 Andrei Tatarnikov
11
In SMT solvers, a special functional language is used to specify constraints. The constraint solver subsystem generates constructions in the SMT language and runs the engine to process them and produce the results (find values of unknown input variables).
12
13 1 Andrei Tatarnikov
h2. Constraints and SMT
14
15
Constrains specified as an SMT model are represented by a set of assertions (formulas) that must be satisfied. An SMT solver checks the satisfiability of the model and suggests a solution (variable values) that would satisfy the model. In the example below, we specify a model that should help us create a test that will cause a MIPS processor to generate an exception. We want to find values of the rs and rt general purpose registers that will cause the ADD instruction to raise an integer overflow exception. It should be correct 32-bit signed integers that are not equal to each other. Here is an SMT script:
16
17 18 Andrei Tatarnikov
<pre>
18 1 Andrei Tatarnikov
(define-sort        Int_t () (_ BitVec 64))
19
20
(define-fun      INT_ZERO () Int_t (_ bv0 64))
21
(define-fun INT_BASE_SIZE () Int_t (_ bv32 64))
22
(define-fun INT_SIGN_MASK () Int_t (bvshl (bvnot INT_ZERO) INT_BASE_SIZE))
23
24
(define-fun IsValidPos ((x!1 Int_t)) Bool (ite (= (bvand x!1 INT_SIGN_MASK) INT_ZERO) true false))
25
(define-fun IsValidNeg ((x!1 Int_t)) Bool (ite (= (bvand x!1 INT_SIGN_MASK) INT_SIGN_MASK) true false))
26
(define-fun IsValidSignedInt ((x!1 Int_t)) Bool (ite (or (IsValidPos x!1) (IsValidNeg x!1)) true false))
27
28
(declare-const rs Int_t)
29
(declare-const rt Int_t)
30
31
; rt and rs must contain valid sign-extended 32-bit values (bits 63..31 equal)
32
(assert (IsValidSignedInt rs))
33
(assert (IsValidSignedInt rt))
34
35
; the condition for an overflow: the summation result is not a valid sign-extended 32-bit value
36
(assert (not (IsValidSignedInt (bvadd rs rt))))
37
38
; just in case: rs and rt are not equal (to make the results more interesting)
39
(assert (not (= rs rt)))
40
41
(check-sat)
42
43
(echo "Values that lead to an overflow:")
44
(get-value (rs rt))
45 18 Andrei Tatarnikov
</pre>
46 1 Andrei Tatarnikov
47 5 Andrei Tatarnikov
In an ideal case, each run of an SMT solver should return random values from the set of possible solutions. This should improve test coverage. Unfortunately, the current implementation is limited to a single solution that is constant for all run. This should be improved in the final version.
48
49 9 Sergey Smolov
h3. SMT Limitations.
50 5 Andrei Tatarnikov
51 8 Andrei Tatarnikov
# *Recursion in not allowed* in SMT-LIB. At least, this applies to the Z3 implementation. In other words, code like provided below is not valid:
52 5 Andrei Tatarnikov
53
<pre>
54
(define-fun fact ((x Int)) Int (ite (= x 0) 1 (fact (- x 1))))
55
(simplify (fact 10))
56
</pre>
57 1 Andrei Tatarnikov
58 12 Andrei Tatarnikov
h3. Constraints in XML
59
60 20 Andrei Tatarnikov
Constraints can also be described in the XML format. The API provides functionality to load and save constraints in XML. Here is an example of an XML document describing a simple constraint.
61 19 Andrei Tatarnikov
62 15 Andrei Tatarnikov
<pre><code class="xml">
63 12 Andrei Tatarnikov
<?xml version="1.0" encoding="UTF-8" standalone="no"?>
64 1 Andrei Tatarnikov
<Constraint version="1.0">
65 16 Andrei Tatarnikov
    <Name>SimpleBitVector</Name>
66
    <Description>SimpleBitVector constraint</Description>
67 13 Andrei Tatarnikov
    <Solver id="Z3_TEXT"/>
68 1 Andrei Tatarnikov
    <Signature>
69 16 Andrei Tatarnikov
        <Variable length="3" name="a" type="BIT_VECTOR" value=""/>
70
        <Variable length="3" name="b" type="BIT_VECTOR" value=""/>
71 13 Andrei Tatarnikov
    </Signature>
72 1 Andrei Tatarnikov
    <Syntax>
73 12 Andrei Tatarnikov
        <Formula>
74 13 Andrei Tatarnikov
            <Expression>
75 16 Andrei Tatarnikov
                <Operation family="ru.ispras.solver.core.syntax.EStandardOperation" id="NOT"/>
76 1 Andrei Tatarnikov
                <Expression>
77 16 Andrei Tatarnikov
                    <Operation family="ru.ispras.solver.core.syntax.EStandardOperation" id="EQ"/>
78
                    <VariableRef name="a"/>
79 1 Andrei Tatarnikov
                    <VariableRef name="b"/>
80
                </Expression>
81
            </Expression>
82 12 Andrei Tatarnikov
        </Formula>
83 1 Andrei Tatarnikov
        <Formula>
84
            <Expression>
85
                <Operation family="ru.ispras.solver.core.syntax.EStandardOperation" id="EQ"/>
86 13 Andrei Tatarnikov
                <Expression>
87 16 Andrei Tatarnikov
                    <Operation family="ru.ispras.solver.core.syntax.EStandardOperation" id="BVOR"/>
88
                    <VariableRef name="a"/>
89
                    <VariableRef name="b"/>
90 1 Andrei Tatarnikov
                </Expression>
91 16 Andrei Tatarnikov
                <Value length="3" type="BIT_VECTOR" value="111"/>
92 13 Andrei Tatarnikov
            </Expression>
93 12 Andrei Tatarnikov
        </Formula>
94 13 Andrei Tatarnikov
        <Formula>
95
            <Expression>
96 16 Andrei Tatarnikov
                <Operation family="ru.ispras.solver.core.syntax.EStandardOperation" id="EQ"/>
97 12 Andrei Tatarnikov
                <Expression>
98 16 Andrei Tatarnikov
                    <Operation family="ru.ispras.solver.core.syntax.EStandardOperation" id="BVLSHL"/>
99
                    <VariableRef name="a"/>
100
                    <Value length="3" type="BIT_VECTOR" value="011"/>
101 12 Andrei Tatarnikov
                </Expression>
102 16 Andrei Tatarnikov
                <Expression>
103
                    <Operation family="ru.ispras.solver.core.syntax.EStandardOperation" id="BVSMOD"/>
104
                    <VariableRef name="a"/>
105
                    <Value length="3" type="BIT_VECTOR" value="010"/>
106
                </Expression>
107 13 Andrei Tatarnikov
            </Expression>
108
        </Formula>
109 12 Andrei Tatarnikov
        <Formula>
110 13 Andrei Tatarnikov
            <Expression>
111 16 Andrei Tatarnikov
                <Operation family="ru.ispras.solver.core.syntax.EStandardOperation" id="EQ"/>
112
                <Expression>
113
                    <Operation family="ru.ispras.solver.core.syntax.EStandardOperation" id="BVAND"/>
114
                    <VariableRef name="a"/>
115
                    <VariableRef name="b"/>
116
                </Expression>
117
                <Value length="3" type="BIT_VECTOR" value="000"/>
118 12 Andrei Tatarnikov
            </Expression>
119 1 Andrei Tatarnikov
        </Formula>
120 12 Andrei Tatarnikov
    </Syntax>
121 14 Andrei Tatarnikov
</Constraint>
122 15 Andrei Tatarnikov
</code></pre>
123 1 Andrei Tatarnikov
124 21 Andrei Tatarnikov
The same constraint described in SMT-LIB looks like this:
125
126
<pre>
127
(declare-const a (_ BitVec 3))
128
(declare-const b (_ BitVec 3))
129
(assert (not (= a b)))
130
(assert (= (bvor a b) #b111))
131
(assert (= (bvand a b) #b000))
132
(assert (= (bvshl a (_ bv3 3))(bvsmod a (_ bv2 3))))
133
(check-sat)
134
(get-value (a b))
135
(exit)
136
</pre>
137
138 1 Andrei Tatarnikov
h2. Tree Representation
139
140
In our system, we use context-independent syntax trees to represent constraints. These trees are then used to generate a representation that can be understood by a particular SMT solver. Generally, it is an SMT model that uses some limited set of solver features applicable to microprocessor verification. The syntax tree contains nodes of the following types:
141
# Constraint. This is the root node of the tree. It holds the list of unknown variables and the list of assertions (formulas) for these variables.
142
# Formula. Represents an assertion expression. Can be combined with other formulas to build a more complex expression (by applying logic OR, AND or NOT to it). The underlying expression must be a logic expression that can be solved to true or false.
143
# Operation. Represents an unary or binary operation with some unknown variable, some value or some expression as parameters.
144
# Variable.Represents an input variable. It can have an assigned value and, in such a case, will be treated as a value. Otherwise, it is an unknown variable. A variable includes a type as an attribute.
145
# Value. Specifies some known value of the specified type which can be accessed as an attribute.
146
147
Note: Operation, Variables and Value are designed to be treated polymorphically. This allows combining them to build complex expressions.
148
149
h2. Constraint Solver Java Library
150
151
The Constraint Solver subsystem is implemented in Java. The source code files are located in the "microtesk++/constraint-solver" folder. The Java classes are organized in the following packages:
152
# ru.ispras.microtesk.constraints - contains SMT model generation logic and solver implementations.
153
# ru.ispras.microtesk.constraints.syntax - contains classes implementing syntax tree nodes.
154
# ru.ispras.microtesk.constraints.syntax.types - contains code that specifies particular data types and operation types.
155
# ru.ispras.microtesk.constraints.tests - contains JUnit test cases.
156
157
h3. Core classes/interfaces
158
159
*Syntax Tree Implementation*
160
161
The syntax tree nodes are implemented in the following classes:
162
* Constraint. Parameterized by a collection of Variable objects and a collection of Formula objects.
163
* Formula. Parameterized by an Operation object.
164
* Operation. Implements SyntaxElement. Parameterized by operand objects implementing SyntaxElement and an operation type object implementing OperationType.
165
* Variable. Implements SyntaxElement. Parameterized by the variable name string, a data type object implemeting DataType and a BigInteger value object.   
166
* Value. Implements SyntaxElement. Parameterized a data type object implemeting DataType and a BigInteger value object.
167
168
The SyntaxElement interface provides the ability to combine different kinds of elements into expressions.
169
170 10 Alexander Kamkin
The current implementation supports operations with the following data types: (1) Bit vectors, (2) Booleans. They are implemented in the BitVector and LogicBoolean classes. The BitVectorOperation and LogicBooleanOperation classes specify supported operation with these types. For example, the LogicBooleanOperation class looks like this:
171 1 Andrei Tatarnikov
172
<pre><code class="java">
173
public final class LogicBooleanOperation extends OperationType
174
{
175
	private LogicBooleanOperation() {}
176
	
177
	/** Operation: Logic - Equality */
178
	public static final OperationType EQ = new LogicBooleanOperation();
179
	/** Operation: Logic - AND */
180
	public static final OperationType AND = new LogicBooleanOperation();
181
	/** Operation: Logic - OR */
182
	public static final OperationType OR  = new LogicBooleanOperation();
183
	/** Operation: Logic - NOT */
184
	public static final OperationType NOT = new LogicBooleanOperation();
185
	/** Operation: Logic - XOR */
186
	public static final OperationType XOR = new LogicBooleanOperation();
187
	/** Operation: Logic - Implication */
188 10 Alexander Kamkin
	public static final OperationType IMPL= new LogicBooleanOperation();
189 1 Andrei Tatarnikov
} 
190
</code></pre>
191
192 10 Alexander Kamkin
The code below demonstrates how we can build a syntax tree representation for the integer overflow constraint:
193 1 Andrei Tatarnikov
194
<pre><code class="java">
195
class BitVectorIntegerOverflowTestCase implements SolverTestCase
196
{
197
	private static final int      BIT_VECTOR_LENGTH = 64;
198
	private static final DataType   BIT_VECTOR_TYPE = DataType.getBitVector(BIT_VECTOR_LENGTH);
199
	private static final Value             INT_ZERO = new Value(new BigInteger("0"), BIT_VECTOR_TYPE);
200
	private static final Value        INT_BASE_SIZE = new Value(new BigInteger("32"), BIT_VECTOR_TYPE);
201
202
	private static final Operation    INT_SIGN_MASK =
203
		new Operation(BitVectorOperation.BVSHL, new Operation(BitVectorOperation.BVNOT, INT_ZERO, null), INT_BASE_SIZE);
204
	
205
	private Operation IsValidPos(SyntaxElement arg)
206
	{
207
		return new Operation(LogicBooleanOperation.EQ, new Operation(BitVectorOperation.BVAND, arg, INT_SIGN_MASK), INT_ZERO);
208
	}
209
	
210
	private Operation IsValidNeg(SyntaxElement arg)
211
	{
212
		return new Operation(LogicBooleanOperation.EQ, new Operation(BitVectorOperation.BVAND, arg, INT_SIGN_MASK), INT_SIGN_MASK);
213
	}
214
	
215
	private Operation IsValidSignedInt(SyntaxElement arg)
216
	{
217
		return new Operation(LogicBooleanOperation.OR, IsValidPos(arg), IsValidNeg(arg));
218
	}
219
	
220
	public Constraint getConstraint()
221
	{
222
		Constraint constraint = new Constraint();
223
		
224
		Variable rs = new Variable("rs", BIT_VECTOR_TYPE, null);
225
		constraint.addVariable(rs);
226
		
227
		Variable rt = new Variable("rt", BIT_VECTOR_TYPE, null);
228
		constraint.addVariable(rt);
229
		
230
		
231
		constraint.addFormula(
232
			new Formula(
233
				IsValidSignedInt(rs)
234
			)
235
		);
236
		
237
		constraint.addFormula(
238
			new Formula(
239
				IsValidSignedInt(rt)
240
			)
241
		);
242
243
		constraint.addFormula(
244
			new Formula(
245
				new Operation(
246
					LogicBooleanOperation.NOT,
247
					IsValidSignedInt(new Operation(BitVectorOperation.BVADD, rs, rt)),
248
					null
249
				) 
250
			)
251
		);
252
253
		constraint.addFormula(
254
			new Formula(
255
				new Operation(LogicBooleanOperation.NOT, new Operation(LogicBooleanOperation.EQ, rs, rt), null)
256
			)
257
		);
258
259
		return constraint;
260
	}
261
	
262
	public Vector<Variable> getExpectedVariables()	
263
	{
264
		Vector<Variable> result = new Vector<Variable>();
265
		
266
		result.add(new Variable("rs", BIT_VECTOR_TYPE, new BigInteger("000000009b91b193", 16)));
267
		result.add(new Variable("rt", BIT_VECTOR_TYPE, new BigInteger("000000009b91b1b3", 16)));
268
		
269
		return result;	
270 10 Alexander Kamkin
	}
271 1 Andrei Tatarnikov
}
272
</code></pre>
273
274
*Representation Translation*
275
276 10 Alexander Kamkin
The logic that translates a tree representation into an SMT representation is implemented in the following way: Methods of the Translator class traverse the constraint syntax tree and use methods of the RepresentationBuilder interface to translate information about its nodes into a representation that can be understood by a particular solver. The RepresentationBuilder interface looks like follows:
277 1 Andrei Tatarnikov
278
<pre><code class="java">
279
public interface RepresentationBuilder
280
{	
281
	public void addVariableDeclaration(Variable variable);
282
283
	public void beginConstraint();
284
	public void endConstraint();
285
286
	public void beginFormula();
287
	public void endFormula();
288
289
	public void beginExpression();
290
	public void endExpression();
291
292
	public void appendValue(Value value);
293
	public void appendVariable(Variable variable);
294 10 Alexander Kamkin
	public void appendOperation(OperationType type);
295 1 Andrei Tatarnikov
}
296
</code></pre>
297
298
*Solver Implementation*
299
300 10 Alexander Kamkin
Solvers use the Translator class and a specific implementation of the RepresentationBuilder interface to generate an SMT representation of a constraint. Then they run a solver engine to solve the constraint and produce the results. Solver implement a common interface called Solver that looks like this:
301 1 Andrei Tatarnikov
302
<pre><code class="java">
303
public interface Solver
304
{
305
	public boolean solveConstraint(Constraint constraint);
306
	
307
	public boolean isSolved();
308
	public boolean isSatisfiable();
309
	
310
	public int getErrorCount();
311
	public String getErrorText(int index);
312
	
313
	public int getVariableCount();
314 10 Alexander Kamkin
	public Variable getVariable(int index);
315 1 Andrei Tatarnikov
}
316
</code></pre>