Control Flow Protection Using Abstract Signatures

Low Cost Control Flow Protection Using Abstract Control Signatures Daya S Khudia and Scott Mahlke University of Michigan University of Michigan 1 Electrical Engineering and Computer Science

Soft Errors Soft errors, also called single-event upsets(SEUs) Occur because of High energy particle strikes or electrical noise Parameters affecting soft error rates Shrinking dimensions, Voltage scaling 100 times increase from 180nm to 16nm (Borkar, Micro 05). One failure per day every chip at 16nm (Feng et al, ASPLOS 10) Image credit: Certichip 2 University of Michigan Electrical Engineering and Computer Science

Soft Error Detection Control flow Data flow Increasing Overhead DMR, TMR DMR, TMR ~100-200% Signature/assertion based (CFCSS, ACFC) Instruction duplication (SWIFT, EDDI) ~30-70% Instruction duplication + hardware symptoms (Shoestring, profileBased) Target Solution ~10-30% Redundant execution in a single-threaded context Compiler interleaves original and redundant instructions Comparable coverage Usually by embedding signatures/assertions in basic blocks Improved by using profiling Mission-critical reliability Our target is a low-overhead control flow protection solution Software-based control flow protection Combine duplication and symptoms Traditional dual/triple modular redundancy University of Michigan 3 Electrical Engineering and Computer Science

Why Control Flow Errors? More than 70% of the transient faults lead to control flow errors (Vahdatpour et al.) Faults in hardware components manifest as control flow errors Program counter Address circuitry Correct executions Incorrect executions Control Flow Target Errors Data Flow Errors 10% Errors in branch targets are 2.5x more likely to result in incorrect executions 0% 20% 30% 40% 50% 60% 70% 80% 90% 100% % of runs University of Michigan 4 Electrical Engineering and Computer Science

Outline Background Software-based control flow checking Abstract Control Signatures (ACS) Experimental evaluation Conclusions 5 University of Michigan Electrical Engineering and Computer Science

Control Flow Checking Two steps for control flow checking Compute signature at runtime Compare with an expected correct value BB1 update sig var check sig var BB2 update sig var check sig var In case of illegal control flow transfer, the signature check fails University of Michigan 6 Electrical Engineering and Computer Science

Signature-Based Control Flow Checking Software-based control flow checking Update signature in each basic block Check signature in each basic block Can only handle errors in branch targets Errors in branch directions (conditions) are not covered s1 d1 = - - - BB1 G = G xor d1 G = = s1? s2 d2 = s1 xor s2 BB2 G = G xor d2 G = = s2? G = G xor d2 G = s1 xor s1 xor s2 G = s2 University of Michigan 7 Electrical Engineering and Computer Science

Signature-Based Control Flow Checking s1 d1 = - - - BB1 G = G xor d1 G = G xor D2 D1 = 0 s3 d3 = s- xor s3 BB3 G = G xor d3 D1 = s1 xor s3 G = = s3? G = = s1? BB2 G = G xor d2 G = G xor D1 For branch fan-in nodes Extra updates Dynamically adjusting signature are required s2 d2 = s1 xor s2 G = = s2? University of Michigan 8 Electrical Engineering and Computer Science

Abstract Control Signatures Sources of overhead Signature updates Signature checks BB1 G = G xor d1 G = G xor D2 D1 = 0 BB3 G = G xor d3 D1 = s1 xor s3 G = = s3? Abstract away the details of control flow inside a region Form regions G = = s1? BB2 G = G xor d2 G = G xor D1 G = G xor d4 D2 = s2 xor s6 BB4 G = = s2? G = = s4? BB5 G = G xor d5 D3 = s4 xor s7 G = = s5? University of Michigan 9 Electrical Engineering and Computer Science

Abstract Control Signatures Sources of overhead Signature updates Signature checks BB1 G = G xor d1 G = G xor D2 D1 = 0 Sig update BB3 G = G xor d3 D1 = s1 xor s3 G = = s3? Sig update G = = s1? BB2 G = G xor d2 G = G xor D1 Sig update Form regions Abstract away the details of control flow inside a region G = = s2? Optimize signature updates check simple run-time properties Optimize checks Insert checks at region boundaries BB4 G = G xor d4 D2 = s2 xor s6 Sig check Sig update G = = s4? BB5 G = G xor d3 D3 = s4 xor s7 Sig update G = = s5? University of Michigan 10 Electrical Engineering and Computer Science

Insight 1: Optimized updates Signature checking Make sure that control flow transfer took place from a legal predecessor bb1 C1 = 1 bb2 C1 = C1 + 1 bb3 bb4 Check counters (path length) Makes sure that proper number of BBs in predecessor region were visited C1 = = 4? C1 = C1 + 1 C1 = C1 + 1 bb5 C1 = C1 + 1 bb6 C1 = C1 + 1 C1 = = 5? University of Michigan 11 Electrical Engineering and Computer Science

Insight 2: Optimized checks Interval 1 bb1 Sufficient to have a single check for a group of basic blocks bb2 bb3 Requirement on regions The header block of a region should dominate all the BBs in that region (single entry point) Nested loops should not be contained in a region bb4 Interval 2 bb_latch1 bb_latch2 University of Michigan 12 Electrical Engineering and Computer Science

Balancing Increments Naively inserting checks Multiple counter value bb1 checks would be required at exits Insert extra increment along these edges C1 = 1 bb2 C1 = C1 + 1 bb3 C1 = C1 + 1 C1 = C1 + 1 Developed an algorithm to get (details are in paper) increment edges increment amounts C1 = C1 + 1 bb4 C1 = C1 + 1 bb5 C1 = C1 + 1 C1 = = 3 or 4? C1 = = 5? C1 = = 4 or 5? C1 = = 5? University of Michigan 13 Electrical Engineering and Computer Science

Optimization for Loops bbN C1 = 0 bb1 bb1 C1 = 1 C1 = C1 + 1 bb2 bb4 bb2 bb3 C1 = C1 + 1 C1 = C1 + 1 C1 = C1 + 1 C1 = C1 + 1 bb4 bb4 C1 = C1 + 1 C1 = C1 + 1 C1 = C1 + 2 C1 == 3? C1 / 3 == 0? C1 % 4 == 0? Move checks out of the loop Insert increments Such that counter value is a power of two (facilitates remainder operation instead of costly division) University of Michigan 14 Electrical Engineering and Computer Science

Handling Call and Return Insts Every function in the program is assigned a unique path length Global Signature variable is Updated before and inversely updated after call Inversely updated and updated inside callee call foo; foo: Entry_BB inverse update sig var update sig var with call specific length call foo; Inverse update with call specific length check sig var Ret_BB update sig var return; University of Michigan 15 Electrical Engineering and Computer Science

System Overview Compilation Collect required program information Analyze program structure Insert signature updates and checks Insert signature updates and checks Runtime Trigger lightweight recovery based on selective symptoms (hardware exceptions) signature comparison fails Operating System Physical Hardware 16 University of Michigan Electrical Engineering and Computer Science

Evaluation Methodology Program analysis and signatures updates/checks Implemented as compiler pass in the LLVM compiler SPECINT2K Benchmarks Statistical fault injection (SFI) experiments GEM5 simulator in ARM syscall emulation mode Random (single) bit flip in control flow target Simulated entire benchmarks after fault injection Log files analyzed for results classification 17 University of Michigan Electrical Engineering and Computer Science

Performance Overhead CFCSS CFCSS_ivl ACS ACS + calls_rets 160% Performance Overhead (runtime) 140% 120% 100% 80% 60% 40% 20% 0% The performance overhead is down from 75% to 11% University of Michigan 18 Electrical Engineering and Computer Science

Fault Coverage Masked CFDetects HWDetects Failures SDCs 100% 90% 80% 70% % of runs 60% 50% 40% 30% 20% 10% 0% ACS ACS ACS ACS ACS ACS ACS ACS ACS ACS ACS ACS CFCSS_ivl CFCSS_ivl CFCSS_ivl CFCSS_ivl CFCSS_ivl CFCSS_ivl CFCSS_ivl CFCSS_ivl CFCSS_ivl CFCSS_ivl CFCSS_ivl CFCSS_ivl CFCSS CFCSS CFCSS CFCSS CFCSS CFCSS CFCSS CFCSS CFCSS CFCSS CFCSS CFCSS ACS + calls_rets ACS + calls_rets ACS + calls_rets ACS + calls_rets ACS + calls_rets ACS + calls_rets ACS + calls_rets ACS + calls_rets ACS + calls_rets ACS + calls_rets ACS + calls_rets ACS + calls_rets 164.gzip On average, fault coverage of ACS is comparable to CFCSS with almost 7x reduction in overhead 175.vpr 176.gcc 181.mcf 186.crafty 197.parser 253.perl 254.gap 255.vortex 256.bzip2 300.twolf average University of Michigan 19 Electrical Engineering and Computer Science

Fault Detection Latency WithIn2K Within10K WithIn100K 1.25 1.20 Normalized detection latency 1.15 1.10 1.05 1.00 0.95 0.90 0.85 0.80 CFCSS CFCSS CFCSS CFCSS CFCSS maximum of 5% CFCSS CFCSS CFCSS CFCSS CFCSS CFCSS CFCSS ACS ACS ACS ACS ACS ACS ACS ACS ACS ACS ACS ACS Fault detection latency is affected by a 164.gzip 175.vpr 176.gcc 181.mcf 186.crafty197.parser 253.perl 254.gap 255.vortex256.bzip2 300.twolf average University of Michigan 20 Electrical Engineering and Computer Science

Conclusions We propose Abstract Control Signatures (ACS) Signature checking at coarse-grain Simplified signature updates In comparison to a traditional signature based scheme (CFCSS) Reduces performance overhead from 75% down to 11% Fault coverage is comparable University of Michigan 21 Electrical Engineering and Computer Science

22 University of Michigan Electrical Engineering and Computer Science

Fault Injection Outcome Classification Masked No corruption in the program output CFDetects Detected by control flow checking Covered by symptoms (HWDetects) Produces a symptom such as page fault in 2000 cycles of fault injection Failures Fail status on program termination or infinite loop. SDCs (Silent Data Corruptions) Fault injections which results in user visible corruptions 23 University of Michigan Electrical Engineering and Computer Science