Optimizing IPOG's Vertical Growth with Hypergraph Coloring

Optimizing IPOGs Vertical Growth with Constraints Based on Hypergraph Coloring Feng Duan, Yu Lei, Linbin Yu, Raghu N. Kacker, D. Richard Kuhn Mar. 13, 2017 1

Outline IPOG s vertical growth with constraints Motivating example Hypergraph Coloring-based optimization How effective is our approach? Conclusion and Future Work 2

Constraints in MFT format Minimum Forbidden Tuple A forbidden tuple (FT) is a tuple that violates constraints A minimum forbidden tuple (MFT) is a forbidden tuple of minimum size that covers no other forbidden tuples For example, given a constraint in logic expression format if (b = 1 and d = 0) or (c = 1) then e != 0 Tuple {b.1, c.0, d.0, e.0} is a FT, and there are many FTs The constraint can be transformed into equivalent set of MFTs: MFT1 = {b.1, d.0, e.0}, MFT2 = {c.1, e.0} A set of constraints can be transformed into a set of MFTs, while the method has already been introduced in our other papers 3

IPOGs Vertical Growth with Constraints Algorithm IPOG-Vertical-Growth Input ts : existing test set : the set of t-way missing tuples involving new parameter p c : constraints in MFT format Output ts : updated test set { 1. for (each tuple in set ){ 2. if (there exists a test in test set tsthat can be changed to a test that covers both and , i.e., is compatiblewith , and is valid on c) { 3. replace test with in ts 4. remove from the tuples covered by 5. } else { 6. add a new test only contains into ts 7. remove from the tuples covered by 8. } // end if at line 2 9. } // end for at line 1 10. return ts; } 4

IPOG-Vertical-Growth vs. Vertex Coloring IPOG-Vertical-Growth is a tuple-oriented algorithm cover each missing tuple in an arbitrary order by filling it into an existing test or creating a new test If we consider missing tuples as uncolored vertices existing tests as colored vertices with distinct colors then IPOG-Vertical-Growth can be considered as a greedy algorithm for vertex coloring after coloring, each group of vertices in the same color is equivalent to a final test The challenge of vertical growth is to minimize the number of new tests can be modeled as a classical NP-hard problem called Minimum Vertex Coloring 5

From Our Previous Work In our earlier work, we have already reduced vertical growth problem to Graph Coloring missing tuples -> uncolored vertices existing tests -> colored vertices with distinct colors compatibility conflicts -> edges conflict between two missing tuples, or between one existing test and one missing tuple two vertices are incompatible due to they assign different values on the same parameter We did not consider validity conflicts, i.e., conflicts that are due to constraints a validity conflict is difficult to handle in a classical graph coloring problem it may involve more than two vertices and thus cannot be represented as an edge in a graph The key challenge of our approach is to extract validity conflicts from constraints and model them for coloring 6

Graph vs. Hypergraph In mathematics, a hypergraph is a generalization of a graph in which an edge can join any number of vertices while edge in graph can only join two vertices Later, we will represent validity conflicts as hypergraph edges (abbr. hyperedges) compatibility conflicts will also be represented as edges but each always joins two vertices 7

Outline IPOG s vertical growth with constraints Motivating example Hypergraph Coloring-based optimization How effective is our approach? Conclusion and Future Work 8

Ideal Vertical Growth Phase Assume an ideal vertical growth phase for motivating example, which begins with empty test set Divide all missing tuples into different groups such that all the tuples in the same group involve the same value of the new parameter allow us to divide the vertical growth problem into multiple independent sub-problems each sub-problem tries to generate tests to cover one group of missing tuples Motivating example is a solution for one sub- problem 9

Motivating Example An example to show why vertical growth can be improved for the t-way generation Let t=3, f be the new parameter and f.1 be its second value the group of six missing tuples involving f.1 is shown in the left table two constraints in MFT format: MFT1 = {b.1, d.0, e.0}, MFT2 = {c.1, e.0} In its conflict hypergraph as the right figure an edge (solid line) between two vertices represents a compatibility conflict two missing tuples are incompatible, i.e., assign different values on same parameter a hyperedge (dashed closed curve) enclosing multiple vertices represents a validity conflict these missing tuples are compatible, but their combination violates constraints, i.e., it contains at least one MFT b, c c b t1 t2 t3 t4 t6 t5 x, y compatibility conflict validity conflict 10

Different Orders for Covering Tuples If we try to cover these missing tuples in a default order (t1, t2, t3, t4, t5, t6), we get 3 tests as shown in the top table Note that, since tuples causing any conflict cannot be put into the same test, new test may be created to cover the ingoing tuple if no existing test is available t6 b, c c b t1 t2 t3 t4 t5 Our previous Graph Coloring-based (GC) approach only counts the degree of compatibility conflicts (as the number of involved edges) for each vertex. Thus, degree(t1) = 1, degree(t2) = 2, degree(t3) = 1, degree(t4) = 2, degree(t5) = 0, degree(t6) = 0. Using these degrees, we obtain the GC order as (t2, t4, t1, t3, t5, t6), which results in 3 tests as shown in the middle table x, y compatibility conflict validity conflict However, if the tuples are covered in the following order (t4, t2, t6, t1, t3, t5), only 2 tests are needed to cover all of them, as shown in the bottom table 11

Intuition of Covering Order and Degree of Conflicts The intuition is that we should cover tuples which involve more conflicts earlier since these tuples are more strictly restrained by other missing tuples, existing tests, constraints and thus have less freedom in terms that fewer tests can be used to cover these tuples Degree of Conflicts (DOC) Calculate the DOC for each uncolored vertex involved in edges/hyperedges The calculation on edges is quite simple and done in previous work How to extract hyperedges from constraints? How to use hyperedges to determine the order while they may be of different sizes? Deploy greedy coloring method to color vertices in the non- increasing order of DOC i.e., the higher the DOC of a vertex is, the earlier it is colored 12

Outline IPOG s vertical growth with constraints Motivating example Hypergraph Coloring-based optimization How effective is our approach? Conclusion and Future Work 13

Hypergraph Coloring Hypergraph coloring is assigning one of the colors from a color set to every vertex in such a way that each hyperedge contains at least two vertices of distinct colors In other words, all vertices in a hyperedge cannot have only one color if the number of its vertices is no less than two In this sense, hypergraph coloring is a direct generalization of graph coloring 14

Reduction to Hypergraph Coloring As mentioned before, IPOG-Vertical-Growth can be reduced to greedy coloring on a hypergraph such that missing tuples -> uncolored vertices existing tests -> colored vertices with distinct colors compatibility conflicts -> edges validity conflicts -> hyperedges After hypergraph coloring, each group of vertices in the same color is exactly a test 15

How to Extract Hyperedges from Constraints? Before extract hyperedges, we have to first extract edges as a conflict matrix by checking every pair of vertices Presented in our previous paper If constraints are given in MFT format, then a hyperedge is a subset of vertices whose values contain an MFT it can be a combination of vertices all of which are missing tuples, or one is an existing test and the others are missing tuples 16

How to Extract Hyperedges from Constraints? (2) There are three fundamental properties of hyperedges in conflict hypergraph The size of a hyperedge is no less than 2 A hyperedge should not contain any edge as compatibility conflict i.e., vertices in a hyperedge should be compatible A hyperedge should not contain any smaller-size hyperedge i.e., only minimum hyperedges can be used to represent validity conflicts The principle of hyperedge production is that While grouping on new parameter value, every vertex in a hyperedge should contribute at least one unique old parameter value to cover the MFT. Otherwise, this hyperedge is not minimum 17

How to Extract Hyperedges from Constraints? (3) Hyperedge production for extracting validity conflicts from MFTs are as follows For each MFT, produce minimum hyperedges that contain all old parameter values of the MFT first, for each old parameter value of the MFT, based on the principle of hyperedge production, collect vertices containing that value as a set, such as sets V1, V2, V3, ... for old parameters p1, p2, p3, ... then, do cross product on these sets, such as V1 V2 V3 ..., save all elements in cross product as hyperedge candidates finally, check candidates to remove those who contain edges or contain smaller-size candidates Repeat above step until all MFTs are used for producing hyperedges Remove hyperedges that contain any smaller-size hyperedge The reason why we have to do that in global is because, after all MFTs are used, for a single MFT its hyperedges would be minimum, but they may contain a hyperedge from another MFT 18

How to Extract Hyperedges from Constraints? (4) For example, assume MFT1={a.0, b.0, c.0} in group of f.0, missing tuples are t1={a.0, e.0, f.0}, t2={b.0, e.0, f.0}, t3={c.0, d.0, f.0}, t4={a.0, c.0, f.0} Its hyperedge production are as follows Vertex sets for old parameter values of MFT1 are V1=[t1, t4] for a.0, V2=[t2] for b.0, V3=[t3, t4] for c.0 Cross product V1 V2 V3=[[t1, t2, t3], [t1, t2, t4], [t4, t2, t3], [t4, t2]] Candidates are c1={t1, t2, t3}, c2={t1, t2, t4}, c3={t4, t2, t3}, c4={t4, t2}, while c2 and c3 should be removed due to they contain c4 So the hyperedges from MFT1 are c1 and c4 19

How to Use Hyperedges to Determine the Coloring Order? After hypergraph is modeled, we compute the Degree of Conflicts (DOC) for each vertex The DOC of vertex v is not the number n of edges/hyperedges which touch v, but a sum of reciprocal of their sizes Si (i=1...n) as weighting, i.e., DOC(v) = ?=1 We use reciprocal of Si because, the less vertices a hyperedge contains, the stricter restriction it is Then sort vertices in the non-increasing order of DOC Sorted vertices can be translated back to a sorted set of missing tuples, in order to replace the set as an input of IPOG-Vertical-Growth It means the vertical growth with optimization will greedily cover missing tuples in DOC order instead of an arbitrary order ?(2/S?) 20

Outline IPOG s vertical growth with constraints Motivating example Hypergraph Coloring-based optimization How effective is our approach? Conclusion and Future Work 21

Experiment Incorporate the Hypergraph Coloring-based (HC) approach into vertical growth with MFT-based constraint handling a revised IPOG algorithm implemented in ACTS Compare with the original IPOG algorithm in ACTS (NIST&UTA, v3.0) PICT (Microsoft, v3.3) Nine real-life systems with constraints Apache, Berkeley, bugzilla, gcc, replace, Spin_S, Spin_V, tcas, Violet ACTS already provides MFT generation method to convert constraints into MFTs 22

Experiment Results Result of 2-way test generation The cells highlighted by gray background indicate the smallest test set sizes produced by PICT and ACTS tools 23

Experiment Results(2) Result of 3-way test generation 24

Outline IPOG s vertical growth with constraints Motivating example Hypergraph Coloring-based optimization How effective is our approach? Conclusion and Future Work 25

Conclusion We modeled hypergraph to capture the conflict relationship among missing tuples and existing tests We presented how to extract higher-degree validity conflicts as hyperedges from constraints how to use hyperedges for optimizing vertical growth Experimental results show that HC-based optimization can further reduce the number of tests generated by IPOG for real-life systems 26

Future Work In the future, we will consider the overhead impact of hyperedge production the number of validity conflicts from a MFT may grow exponentially with strength t and the MFT size We will explore the use of heuristics for extracting validity conflicts in order to cut down the time and space cost of HC-based optimization for high-strength t-way testing, and for systems with large-size MFTs 27

Q&A 28