GreyConE: Scalable test generation framework

ITC 2022 paper presentation slides

1. GreyConE : Greybox Fuzzing + Concolic Execution Guided Test Generation for High Level Designs Mukta Debnath 1 Animesh Basak Chowdhury 2 Debasri Saha 3 Susmita Sur-Kolay 1 1 Advanced Computing and Microelectronics Unit, Indian Statistical Institute, Kolkata-700108, India 2 New York University, New York, USA 3 Calcutta University, Kolkata, India

2. Outline Introduction Emerging of High Level Designs (HLD) Existing HLD Verification Techniques Test-case Generation   Preliminaries and Motivation Code Instrumentation Greybox Fuzzing Concolic Execution Proposed GreyConE Framework Interlaced Fuzzing and Concolic Testing Experiments and Results Conclusion

3. Introduction Semiconductor manufacturing process IC Design High Level Designs Specification Architectural Design Behavioral & Functional  Modelling Logical Implementation Placement &Routing Design Layout Synthesis & Testing C SystemC C++ Object-oriented, concurrent Event-driven simulation semantics h/w-s/w co-design

4. Introduction: SystemC Verification Techniques Methods Primary Limitations Formal Verification 1. Property Checking 2. Model Checking Property formulation, State-space explosion, not scalable Simulation based approaches 1. Assertion based 2. Random testing Requires manual intervention, initial seed design bottleneck 3 Symbolic Execution 4 Concolic execution Path explosion problem, Scalability bottleneck, depends on initial stimuli Mutation Testing Fuzz-base d black-box, white-box, grey-box testing Exhaustiv e Testing, High test generation time Desired by Test Engineers: Innovative validation approaches Table I : Existing Techniques High-quality test case generation High code coverage metrics

5. Motivation Security based testing from software community Greybox Fuzzing Design instrumentation Generate interesting test vectors Concolic Execution Concrete execution Obtain a 1 st order Boolean formula for path constraints Invokes SMT solvers with the Boolean formula to generate test-vectors

6. Preliminaries Algorithm 1: FUZZER( DUT ins -exe , T initial ) Data: DUT ins -exe , T initial , time cut -off Result: T fuzzed T fuzzed ← T initial while time ≤ time cut_off do for τ ∈ T fuzzed do K ← CALCULATE ENERGY( τ ) for i ∈ { 1 , 2 , . . . , K} do τ′ ← MUTATE-SEED( τ ) if IS-INTERESTING( DUT ins -exe , τ′) then T fuzzed ← T fuzzed ∪ τ′ end end end end return T fuzzed Fig 1 : Design Instrumentation Algo 1 : Greybox Fuzzing

7. Preliminaries int foo ( int i , int j){ // i and j symbolic variables int x = 0, y = 0, z ; z = 2* j ; if ( z == i ){ if ( j < 5){ x = -2; y = 2; } else { x = 2; y = 2;} } else { x = -2; y = -2;} return 0; } initial random inputs i =2, j=1 z = 2b Exit Exit Exit 2b == a 2b != a 2b == a && b< 5 x = 2, y = 2 2b == a && b>= 5 x = -2, y = 2 x = -2, y = -2 foo ( i =a , j=b) Example code snippet Concolic execution flow Concolic Execution

8. GreyConE Framework “hard-to-reach state?” Concolic Execution Engine Complex branch condition!! Coverage-guided Greybox Fuzz Engine time > threshold-time time > time-budget GreyConE Higher branch coverage Less # test cases Automated Scalable Less CPU time Instrumented DUT Execution Phases: fuzz 1 - conc 1 - fuzz 2 - conc 2 - fuzz 3 …….

9. Experiments and Results Experiments: SystemC Benchmark: SCBench , S2CBench Three sets of Experiments: Greybox Fuzzing : American Fuzzy Lop (AFL) Concolic Execution: Selective Symbolic Executor (S2E) in concolic mode Proposed Framework: GreyConE combining fuzz testing and concolic testing All Experiments are performed for a time cut -off of 2 hours

10. Benchmark LOC #Test cases Branch cov . (%) Time (in s) fuzz 1 conc 1 fuzz 2 fuzz 1 conc 1 fuzz 2 fuzz 1 conc 1 fuzz 2 ADPCM 270 5 6 - 93.3 100 - 9 39 - AES 429 3 4 4 79.2 83.3 91.7 76 29 51 FFT_fixed 334 3 3 - 81.2 96.9 - 29 137 - IDCT 450 62 137 - 64.8 100 - 7 222 - MD5C 467 5 3 2 87.5 90.6 100 9 34 7 Filter_FIR 176 3 2 7 76.8 87.5 93.8 7 23 37 Interpolation 231 44 - - 100 - - 3 - - Decimation 422 3 2 - 96.8 100 - 12 22 - Kasumi 415 31 23 - 93.3 100 - 10 46 - UART 160 2 15 4 81.2 84.1 88.5 334 136 248 Quick_sort 204 7 - - 100 - - 14 - - TABLE II: GreyConE execution phases Result Data: Experiments and Results

11. Experiments and Results TABLE III: Comparing GreyConE (GCE) with baselines Fig 2: Coverage improvement by GreyConE Results showing coverage improvement by GreyConE

12. Experiments and Results Fig 3: Timing speed-up by GreyConE TABLE III: Comparing GreyConE (GCE) with baselines Results showing run-time speedup by GreyConE

13. Experiments and Results Fig. 4: Branch coverage obtained on SystemC designs while running GreyConE , S2E , AFL over a time period of two hours

14. Conclusion GreyConE is the first work combining fuzzing with concolic testing to reach deeper segments of high level designs for trojan detection GreyConE achieves high branch coverage GreyConE is a scalable framework with respect to time and memory Future works include enhancing GreyConE to low-level netlist (RTL/gate-level) and uncover hardware specifc bugs in the designs. We aim to include exploration of input grammar aware fuzzing and more focus on coverage metrics such as Modified Condition/Decision Coverage (MC/DC) and path coverage.