Page 1Tracking Down Software Program Bugs Using Automatic Anomaly DetectionSudheendra Hangal, Processor Products Group, SunMonica S. Lam, Stanford UniversityICSE-2002Buenos A Orlando, FloridaV1.1Page 2OutlineBackground & MotivationPast WorkDynamic InvariantsDIDUCEDynamic Invariant Detection ∪ Checking EngineDIDUCE experiencesUsesConclusion, Q&APage 3BackgroundSoftware reliability is an increasing problemTraditional input-output interaction with a program is insufficientWhat happens inside the black box ?Can cheap machine cycles help ?ProgramInputsOutputsPage 4Motivation for DIDUCEHow do you debug...a program working correctly on some inputs, fail-ing on others ?""Hmm... What's different about runs which fail ?"a program failing after a long time ?a program you don't even know has a bug ?Large programs written by others and evolved over time (with misleading comments!)DIDUCE successfully tackled these problems on 4 different applications we triedPage 5Past WorkMany bug detection toolsStatic approachese.g. Prefix, Metal, Vault, ESC, etcExhaustive, conservativeNo need for test inputsDynamic approachese.g. Purify, Eraser, assert's, ...Need good test input set, observe only possible behaviorPage 6Invariant SpecificationsMany annotation based approachesIts manual work - users never do it!Usually incompleteUsers may not even know the invariants...... Or may know them wrongly!Programmers rely on passing a test-suite as proof that code worksPage 7Dynamic Invariant DetectionHypothesize a space of invariants associated with the programTest each hypothesis on program runsrule out invariants which do not holdPrior work (Daikon) applied to small pro-gramsApproach is automatic and pervasive......but may be unsound!Page 8Dynamic Invariant CheckingIdea: Close the loopDetect invariants on "presumed-good" runsAutomatically check invariants on other runsReport invariant violationsRefine invariants, as you checkInvariant violations signal anomalies, e.g.:New code executedNew values seen for variablesPage 9Dynamic Invariant Detection U Checking Engine (DIDUCE)Simple, practical, and effective toolAdds instrumentation to Java bytecode To deduce and check invariants on the flyWorks with any compliant JVM2 modes - training and checkingInvariant violations suppressed in training modeTraining continues in checking modeConfidence level associated with invariants and violationsPage 10GUI ScreenshotPage 11DIDUCE InvariantsValues at some types of program pointsObject reads/writesStatic var read/writesMethod call sites and return valuesInvariants associated with Tracked Expres-sions (TEs)Value accessedChange in value (for writes)Runtime type of object being accessedRequires only "local" computationPage 12Tracked ExpressionsClass SomeClass { static int x; int y; ...} Object o = new SomeClass(); Object arr[] = new SomeClass[3]; ...Source codeTracked ExpressionsPage 13Tracked ExpressionsClass SomeClass { static int x; int y; ...} Object o = new SomeClass(); Object arr[] = new SomeClass[3]; ... // static field write SomeClass.x = ... SomeClass.xSomeClass.x' - SomeClass.xFor writes, the variable name (e.g. o.x) refers to its value before the write, while the name with a ’ suffix (e.g. o.x’) refers to its value after the write.Source codeTracked ExpressionsPage 14Tracked ExpressionsClass SomeClass { static int x; int y; ...} Object o = new SomeClass(); Object arr[] = new SomeClass[3]; ... // static field write SomeClass.x = ... // object field read ... = o.y; SomeClass.xSomeClass.x' - SomeClass.xo.yoFor writes, the variable name (e.g. o.x) refers to its value before the write, while the name with a ’ suffix (e.g. o.x’) refers to its value after the write.Source codeTracked ExpressionsPage 15Tracked ExpressionsClass SomeClass { static int x; int y; ...} Object o = new SomeClass(); Object arr[] = new SomeClass[3]; ... // static field write SomeClass.x = ... // object field read ... = o.y; // object array write arr[i] = ... SomeClass.xSomeClass.x' - SomeClass.xo.yoarr[i]T(arr[i]') == T(arr[i])For writes, the variable name (e.g. o.x) refers to its value before the write, while the name with a ’ suffix (e.g. o.x’) refers to its value after the write.Source codeTracked ExpressionsPage 16Tracked ExpressionsClass SomeClass { static int x; int y; ...} Object o = new SomeClass(); Object arr[] = new SomeClass[3]; ... // static field write SomeClass.x = ... // object field read ... = o.y; // object array write arr[i] = ... // procedure call foo (x+1, o);SomeClass.xSomeClass.x' - SomeClass.xo.yoarr[i]T(arr[i]') == T(arr[i]) x+1 o return value of fooFor writes, the variable name (e.g. o.x) refers to its value before the write, while the name with a ’ suffix (e.g. o.x’) refers to its value after the write.Source codeTracked ExpressionsPage 17Default Invariant RepresentationCompact, for speedSpace overhead ∝ static size of programFor each tracked expressionConvert to integer"References map to hashcode of class nameEach expression stores sample value and mask" Mask tracks which bits have remained invariantMeeting value incompatible with current hy-pothesis relaxes the mask/invariant" Mask can be relaxed up to #bits timesPage 18Invariant ConfidenceDefined as:# Samples/# of bits marked invariant by maskHigh if same value observed many times, or with small number of bits changeUsers look at invariant violations with large confidence changes firstPage 19User ExtensionsDefault modes work well in practiceour experiments run in this modeUser can change defaultsbased on class, method, target field/method name, read v/s write, type of value accessed, line number...Change set of tracked expressionsChange invariant representationChange confidence computationWriting a new invariant is 20-30 LoCExamples: Min/Max values, Self loopsPage 20DIDUCE Experiences20337118/13731500Joeq JVM+JIT(SourceForge)834844384 /38430000 +RSA librariesJSSE lib(Java Secure Sockets Layer)613014214 /21421700MailManage + Javamail lib(SourceForge)8−12(10 proc)320410/283300Sun MAJC MP SimulatorSlowdown# Program points instrumented# Classes instr.Lines of codeProgramPage 21MAJC SimulatorSimulator stable, in active useDIDUCE used initial part of run for training; ignored violations in this phaseDIDUCE found 2 otherwise undetected errorsDIDUCE accurately root-caused 3 errorsReported violation on 1 error was missedHappened early, incorrect model was built!Reported 10 corner cases,