mc-imperial / dredd

Framework for evaluating C/C++ compiler testing tools
Apache License 2.0
11 stars 3 forks source link

Consider different non-redundant ROR mutants #303

Open afd opened 1 month ago

afd commented 1 month ago

Dredd implements the optimisations from Table III of this paper:

https://people.cs.umass.edu/~rjust/publ/non_redundant_mutants_jstvr_2014.pdf

@JonathanFoo0523 pointed out here that sometimes the choice of which mutants to keep vs. which to be avoided due to subsumption could be more nuanced.

We should revisit this.

JonathanFoo0523 commented 1 month ago

The paper argument still holds in a op b when both a and b are unsigned int.

If one side of operator is 0 and the other side is an unsigned, we can perform a similar (and simpler) analysis to find non redundant ROR mutations.

WLOG, consider a op 0. We have 2 cases for the value of a: (1) a equal to 0; (2) a larger than 0. The outcome of a op 0 for different op is shown below:

+----+------+-----+------+-----+------+------+
|  a | a!=0 | a>0 | a>=0 | a<0 | a<=0 | a==0 |
+----+------+-----+------+-----+------+------+
|  0 |   F  |  F  |   T  |  F  |   T  |   T  |
+----+------+-----+------+-----+------+------+
| >0 |   T  |  T  |   T  |  F  |   F  |   F  |
+----+------+-----+------+-----+------+------+

Note that: (1) The minimal distance mutation for op that produced the same outcome for 2 cases of a is any mutation that produced different outcome for 2 cases of a. Therefore, the sufficient set of non-redundant mutations for these operators is {eq('!=') and eq('==')}, (2) The minimal distance mutation for op that produced different outcomes for 2 cases of a is any mutation that produced the same outcome for 2 cases of a. Therefore, the sufficient set of non-redundant mutations for these operators is {eq('true') and eq('false')},

Here. eq(op) is the set of equivalent mutations under a op 0 (eg: eq('!=') = {!=, >}).

This could allow us to do simpler check for non-redundant ROR operator for unsigned while avoiding equivalent mutations, as noted here.