Lightweight Data-flow Analysis for Execution-driven Constraint Solving Junaid Haroon Siddiqui Darko Marinov Sarfraz Khurshid
背景 Constraint-based testing Key challenge-valid inputs generation execution-driven solving Wasteful Repeated predicate execution, predicate result
贡献 Lightweight static data-flow analysis for constraint solving Multi-value comparisons Implementation Evaluation
Traditional Korat 1，建立一个要测试的初始结构，执行repok算法； 2，当repok算法执行完后，将field domain中最后一个输入域中的数值改成一个新数值，然后重新执行repok算法； 3，如果最后一个field domain中的数值没有更多的数值，则到前一个field domain中； 4，一直所有的field domain中的数值都执行完。
Koratmulti: multi-value comparisons A multi-value comparison compares a given value against all values in the field domain of a field not yet accessed in the repOk predicate. If a field has already been accessed, the given value can only be compared against its ssigned value and no multi-value comparison can take place.
Koratmulti: multi-value comparisons 条件： 至少有一个可能的结果能够决定哪个repOk predicate能够返回。
Koratmulti: multi-value comparisons
Koratmulti: multi-value comparisons
Technique 主要思路： 对candidate进行判断是否为marked，如果是marked，则不需要执行repOk， repOk的结果就可以知道。 主要方法： 结合Data-flow analysis和Multi-value comparisons，在Multi-value comparisons中使用数据流分析方法，然后用Multi-value comparisons将candidate分为marked和unmarked。
1,followUseChain the accessed value is directly used as one argument of a comparison. 2,br The comparison is used inside an if statement. 3,ret determines if a constant is returned.
Evaloution 1,the number of repOk executions 2,the time it takes to generate valid inputs.
Evaloution