Automatic Program Correction

Automatic Program Correction
Anton Akhi
Friday, July 08, 2011
• Introduction
• Survey of existing tools
Why do we need automatic program
• Even if bug has been found it is still
programmer’s job to think of fix
• Allows to fix bug automatically or provide
high-quality fix suggestions
Isn’t it a magic?
• Tools require failing and passing runs
• Oracle to check if test passes
• Program with bug is not far away from the
right one
Existing tools
• Genetic programming:
– Automatic Program Repair with Evolutionary Computation
– A Novel Co-evolutionary Approach to Automatic Software
Bug Fixing
• Machine learning:
– BugFix
• Contract usage:
– Automated Debugging using Path-Based Weakest
– AutoFix-E
– AutoFix-E2
Automatic Program Repair with
Evolutionary Computation
• W. Weimer, S. Forrest, C. Le Goues, T. Nguyen
• Usage of GP to fix bugs:
– Individuals
– Genetic Operators
– Fitness function
Genetic programming: individuals
• Individual is represented as an abstract syntax
tree and weighted path
• Weighted path is a list of statements visited on
negative test case with weight of every
– 1 if not visited by positive tests
– 0.1 if visited by positive tests
Genetic programming: operators
• Mutation:
– statement on a weighted pass is considered for
mutation with probability proportional to its
– deletion, insertion, swap
• Crossover:
– exchange of subtrees chosen at random between
two individuals
Genetic programming: fitness function
• Weighted sum of test cases passed
• Weight of a negative test is at least as much as
positive test
Minimizing changes
• Trim unnecessary edits
• One-minimal subset of changes is a subset
such that without any of the changes program
will stop passing all the tests
• Use delta debugging to compute one-minimal
subset of changes
Automatic Program Repair with
Evolutionary Computation:
• Needs:
– negative and positive test cases
– oracle
– fault localization
• Uses:
– genetic programming
– Delta debugging
• Method has a lot of criticism
A Novel Co-evolutionary Approach to
Automatic Software Bug Fixing
A. Arcuri and X. Yao
Genetic Programming
Distance Functions
Search Based Software Testing
Genetic Programming
• Genetic Program consists of primitives
• Program is represented in a tree form
• Fitness function to be minimized:
N g 
E g 
f g  
  d P t, g t 
N g   1 E g   1 tTi
• N g  is a number of nodes in a program
• E g  is a number of raised exceptions
• d P t, g t  is a special distance function
Distance Functions
• Works fine
with numbers
and boolean
• Predicates
involving 
and  can be
handled only
in cases small
Search Based Software Testing
• Find tests that make evolutionary programs
• Fitness function for test case to be maximized:
f t   d P t, g t 
• Competitive co-evolution
• First generation: copies of buggy program and
unit tests
• Mutations, crossover, replacement by the
original program
• Penalty for short programs
A Novel Co-evolutionary Approach to
Automatic Software Bug Fixing:
• Needs:
– starting set of unit tests
– oracle
• Uses:
– genetic programming
– co-evolution
– search based software testing
• Some bugs are too difficult to solve
• Bug that is difficult to be fixed by a human
might be very easy for program
BugFix: A Learning-Based Tool to Assist
Developers in Fixing Bugs
D. Jeffrey, M. Feng, N. Gupta, R. Gupta
Association rule learning
Interesting value mapping pairs (IVMP)
Situation descriptors
Knowledgebase of rules
Association rule learning
• Association rule learning is a popular method for
discovering the relationship between variables in
• Association rule X  Y where X, Y are sets of
attributes and X Y   means that if the items
in set X are present then it is probable that the
items in set Y are also present
• The confidence of the rule is
conf  X  Y   supp X  Y  supp X 
where supp(X) is the fraction of transactions
containing X
Interesting Value Mapping Pairs
• An Interesting Value Mapping Pair (IVMP) is a pair
of value mappings (original, alternate) associated
with a particular statement instance in a failing
run, such that: (1) original is the original value
mapping used by the failing run at that instance;
and (2) alternate is an alternate (different) value
mapping such that if the values in original are
replaced by the values in alternate at that
instance during re-execution of the failing run,
then the incorrect output of the failing run
becomes correct
Situation descriptors
• Statement structure situation descriptors
• IVMP pattern situation descriptors
• Value pattern situation descriptors
Statement structure situation
• Unordered tokens comprising the statement
Statement structure situation
descriptors: examples
IVMP pattern situation descriptors
• Consider pattern to occur when corresponding
values in the IVMPs compare to each other in
the same way across all IVMPs at a statement
• Compare in terms less than, greater than, or
equal to
• Look at the pairs of values:
– within original sets of values
– within alternate sets of values
– between corresponding values in sets
IVMP pattern situation descriptors:
Value pattern situation descriptors
• Similar to IVMP patterns
Knowledgebase of rules
• Database of bug-fix scenarios
• Initially created through training data of
known debugging situations
How it works
• Identify rules to consider
– rules in which debugging situation is subset of the
current debugging situation
• Sort rules by confidence values
• Report prioritized bug-fix descriptions
• Learn from current debugging situation and
the corresponding bug fix
BugFix: A Learning-Based Tool to Assist
Developers in Fixing Bugs: Conclusions
• BugFix assists in fixing bugs by producing a list
of bug-fix suggestions
• Tool learns through new situations
• Is not very good with new and logically
difficult bugs
Automated Debugging using
Path-Based Weakest Preconditions
H. He, N. Gupta
Representation of an error trace
Path-based weakest precondition
Hypothesized program state
Actual program state
Detection of evidence
Location and modification of likely errorneous
Representation of an error trace
• i, j is an instance of an executed statement in an
error trace; i is an execution point and j is the line
number of statement
• Branch predicates:
– atomic predicate: (expr relop const)
– compound predicates are in disjunctive normal form:
E  e0    en where ei  g0  g n and gi is an
atomic predicate
• Precondition and postcondition for failing run are
transformed in DNF:
– replace  and  by disjunction and conjunction
Path-based weakest precondition
• pwp(T, R) is the set of all states such that an
execution of function F that flows execution
trace T begun in any of them is guaranteed to
terminate is state satisfying R
• pwp( x  a, R)  Rxa where xa means
substituting every occurrence of x in R with a
• pwp( B, R)  R where B is branch predicate
• pwp(C; D, R)  pwp(C, pwp( D, R))
Hypothesized program state
• Let Ri  pwpT i,n , R where T i,n is a trace from
point i to the end of trace and R is
• Ri defines the set of hypothesized program
states at an execution point i
• Ri  pwpStmti , Ri 1  and Rn  pwpStmtn , R
Actual program state
• Represented by predicates in DNF which are
true for given input
• Consists of forward program states and i
backward program states i
• i i
Forward and backward program states
• Forward program states are defined as:
Q1F  positive conjunctions in precondition
QiF  QiF1  Killi1   Geni1
 QnF  Killn  Genn
Killi and Geni are sets of predicates killed by and
derived from statement Stm ti
• Backward program states are defined as:
– Q  pwpStmt ,Q  if Stm ti is an assignment statement
i 1
– QiB  Stmti  QiB1 if Stm ti is a branch predicate
 
– Qbottom
Detection of evidence
• A is less restrictive than B if A  B is false
• Evidence at point i is situation when Qi is less
restrictive than Ri
• Two types of evidence:
– Explicit
• Type I
• Type II
– Implicit
Types of evidence
• Explicit
– Type I: if at point i in Ri appears negative r in form
(0 relop const) then r forms Eexplicitany, r, i  an
explicit evidence of Type I
– Type II: let q : expr q relop const 1 an atomic predicate in Qi
and r : expr r relop const 2 a negative atomic predicate in Ri
If exprq  exprr then q and r form Eexplicitq, r, i  an explicit
evidence of Type II
• Implicit: negative predicate r in R1 that is not
present in an explicit evidence
Location and modification of likely
erroneous statement
• Use transitivity and equality to deduce new
predicates. New states are Qi* and Ri*
• Explicit Type I
– If = then match r to 0=0. Consider every
assignment statement between i and bottom of
the trace as a possible candidate for modification
– Let rk from Rk* be a corresponding predicate to r,
Stmtk : lhs  rhs and e  lhs  rhs  0 and c  rk 1
– Goal is to make rk  0  0, so pwplhs  rhs, rk 1   0  0
– If rk 1  lhs  rhs  0 then problem is solved
Location and modification of likely
erroneous statement: Explicit Type I
• Consider e and c as a set of strings of characters
• Let de and d c be difference between e and c and
between c and e correspondingly
• If de appears in rhs than replace it with d c
• If de appears in lhs than replace it with d c only if d c
is a single variable
• If none of the above works than select r as e and
try every q from Qi* as c
Location and modification of likely
erroneous statement: Explicit Type II
• Consider Eexplicitq, r, i 
• Either q or r could be in error
• Change the form of r to q at i
– Same manner as above
• Change the form of q to r at i
– Change original branch predicate from which q
may be derived or some assignment statement
– Change of an assignment statement does not
change relop in q
Location and modification of likely
erroneous statement: Implicit
• If there is a loop in the trace, which contributes
some constraints on R1* , and missed constraints
have similarity with constraints added by the
loop then try to derive the possible missing
iterations in the loop
• Try to match negative r from R1* to some q from Q1*
Automated Debugging using
Path-Based Weakest Preconditions:
• Uses contracts
• Can handle only one error
• Cannot handle loops well
Automated Fixing of Programs with
• Yi Wei, Yu Pei, C.A. Furia, L.S. Silva, S.
Buchholz, B. Meyer, A. Zeller
• Assessing Object State
• Fault Analysis
• Behavioral Models
• Generating Candidate Fixes
• Linearly Constrained Assertions
• Validating and Ranking Fixes
Assessing Object State
• Argument-less Boolean Queries
– Absolutely describe state
– Seldom preconditions
– Widely used in Eiffel contracts
• Complex Predicates
– Boolean queries are often correlated
– Implication expresses correlation
– Mine the contracts
– Mutate implications
Fault Analysis
• Find state invariants: passing and failing states
– sets of predicates that hold during all
passing and failing runs respectively
• Fault profile contains all predicates that hold
in the passing run but not in the failing run
• Find the strongest predicate that implies the
negation of violated assertion
Behavioral models
• Finite state automaton
– States are predicates that hold
– Transitions are routines
• Automaton is built based on test runs
• Determine a sequence of routine calls that
change the object state appropriately
• A snippet for a set of predicates is any
sequence of routines that drive object from a
state where none of predicates hold to one
where all of them hold
Generating Candidate Fixes
• Fix Schemas
• snippet is a sequence of routine calls
• old_stmt – some statements in the original
• fail:
– not p
– not p1 and not p2 and
– notviolated_ clause
Linearly Constrained Assertions
• Determine what is variable and what is
• Assign weights:
– Arguments in precondition receive lower weights
– In assertion weight is inversely proportional to the
number of occurrences
– Identifiers that routine can assign receive less
Linearly Constrained Assertions:
Generating fixes
• Select a value for variable that satisfies the
– Look for extremal values
• Plug the value into a fix schema
– if not constraint then new_stmt else old_stmt end
Validating and Ranking Fixes
• Candidate is valid if it passes all the tests
• Two metrics for ranking:
– Dynamic: estimates the difference in runtime
behavior between the fix and the original based
on state distance
– Static: OS  5  SN  2.5  BF
• OS: 0 for schemas (a) and (b) and number of
statements in old_stmt for (c) and (d)
• SN: number of statements in snippet
• BF: number of branches to reach old_stmt from the
point of injection of the instantiated fix schema
Automated Fixing of Programs with
Contracts: Conclusions
• Uses contracts, passing and failing tests to
deduce and suggest bug fixes
• Successfully proposed fixes for 16 out of 42
found bugs in EiffelBase library
Evidence-Based Automated Program
Yu Pei, Yi Wei, C.A. Furia, M. Nordio, B. Meyer
Predicates, Expressions, and States
Static Analysis
Dynamic Analysis
Fixing Actions
Fix Candidate Generation
Validation of Candidates
Predicates, Expressions
• E r is a set of all non-constant expressions in
routine r
• Pr is a set of boolean predicates:
– Boolean expressions: every b  Er
– Voidness checks: e  Void for every e  Er
– Integer comparisons:e ~ e for every e  Er and
every e  Er \ e 0 and ~ in , , 
– Complements  p for every p  Pr
• State Components
– l , p, v - a triple where v is a value of predicate p
for some test case t which riches l
– comp(T) denotes all the triples l , p, v defined by
the tests in the set t  T
Static Analysis
• sub(e) is the set of all sub-expressions of e
• Expression proximity eproxe1 , e2   sube1   sube2 
• Expression dependence between predicate p  Pr
eprox p, c 
and a contract clause c edep p, c  maxeprox , c |   P 
• Control distance cdistl1 ,l2  is the length of the
shortest directed path from l1 to l2 on the
control-flow graph
• Control dependence
cdistl , j 
cdepl , j   1 
maxcdist , j  |   r and  j
Dynamic Analysis
•  t  is a score for tests
•  t   for i-th failing test and  t    i for i-th
passing test; 0   ,   1
• The evidence provided by each test case:
dyn l, p, v     u | u  Fr j,c   v | v  Pr 
Combining Static and Dynamic Analysis
• Combined evidence score:
fixme l , p, v 
edep p, c   cdepl , j   dyn l , p, v
Fixing Actions
• A component l , p, v with a high evidence
score induces a number of possible actions:
– Derived Expressions
– Expression Modification
– Expression Replacement
Fix Candidate Generation
• Candidates are generated in a way similar to
previous method
• Candidate is valid if it passes all the tests
Evidence-Based Automated Program
Fixing: Conclusions
• Uses contracts and sets of passing and failing
• Combines static and dynamic approaches
• Automated Bug Fixing is real!
• Some bugs are still too difficult to fix or even
• All approaches need some kind of oracle;
sometimes contracts are the oracle
• W. Weimer, S. Forrest, C. Le Goues, T. Nguyen,
Automatic Program Repair with Evolutionary
• A. Arcuri and X. Yao, A Novel Co-evolutionary Approach
to Automatic Software Bug Fixing
• D. Jeffrey, M. Feng, N. Gupta, R. Gupta, BugFix: A
Learning-Based Tool to Assist Developers in Fixing Bugs
• H. He, N. Gupta, Automated Debugging using
Path-Based Weakest Preconditions
• Yi Wei, Yu Pei, C.A. Furia, L.S. Silva, S. Buchholz, B.
Meyer, A. Zeller, Automated Fixing of Programs with
• Yu Pei, Yi Wei, C.A. Furia, M. Nordio, B. Meyer,
Evidence-Based Automated Program Fixing

similar documents