Instruction-Grain

1、Flexible Hardware Acceleration for Instruction-Grain Program MonitoringJoint work with Michael Kozuch1, Theodoros Strigkos2, Babak Falsafi3, Phillip B. Gibbons1, Todd C. Mowry1,2, Vijaya Ramachandran4,Olatunji Ruwase2, Michael Ryan1, Evangelos Vlachos2Shimin Chen1Intel Research Pittsburgh 2CMU 3EPFL

2、 4UT AustinFlexible Hardware Acceleration for Instruction-Grain Program MonitoringShimin Chen2Instruction-Grain MonitoringSoftware often contain bugsMemory corruptions, data races, , crashesSecurity attacks often designed to exploit bugsInstruction-grain lifeguards can helpDynamic monitoring: during

3、 application executionInstruction-grain: e.g., memory access, data flowEnables a wide range of powerful lifeguards ApplicationLifeguardFlexible Hardware Acceleration for Instruction-Grain Program MonitoringShimin Chen3Example Instruction-Grain LifeguardsAddrCheck: Monitor malloc/free, memory accesse

4、sCheck if all memory accesses visit allocated memory regionsMemCheck: AddrCheck + check uninitialized valuesCopying partially uninitialized structures is not an errorLazy error detection to avoid many false positives Track propagation of uninitialized valuesTaintCheck: detect overwrite-based securit

5、y exploitsTainted data: data from network or diskTrack propagation of tainted data to detect violationsLockSet: detect data races in parallel programsNethercote04Nethercote & Seward 03 07Savage et al.97Newsome & Song05Flexible Hardware Acceleration for Instruction-Grain Program MonitoringShimin Chen

6、4Design Space of Support PlatformSpecific LifeguardGeneral Purpose: Wide Range of LifeguardsDynamic binary instrumentation (DBI)10-100X slowdownsGeneral-Purpose HW improving DBI3-8X slowdownsLifeguard-specific hardwareThis paperPerformanceGoodPoorBruening04 Luk et al05Nethercote04Crandall & Chong04,

7、 Dalton et al07, Shetty et al06, Shi et al06, Suh et al04, Venkataramani07, Venkataramani08, Zhou et al07Chen et al06 Corliss03Flexible Hardware Acceleration for Instruction-Grain Program MonitoringShimin Chen5OutlineIntroductionBackgroundThree Hardware Acceleration TechniquesExperimental Evaluation

8、ConclusionFlexible Hardware Acceleration for Instruction-Grain Program MonitoringShimin Chen6ApplicationTaintCheck Lifeguardif (taint(F)=1) error;Example Lifeguard: TaintCheckPurpose: detect overwrite-based security exploitsMetadata kept for application memory and registersTainted data: data from ne

9、twork or diskTrack taint propagationDetect violation: e.g., tainted jump target addressmov %eax Amov B %eaxadd %ebx Djmp *(F)taint(%eax) = taint(A)taint(B) = taint(%eax)taint(%ebx)|= taint(D)Newsome & Song05Detect exploit before attack code takes controlFlexible Hardware Acceleration for Instruction

10、-Grain Program MonitoringShimin Chen7TaintCheck w/ Detailed TrackingTaintCheck:Detect violation1 taint bit / application byteTaintCheck w/ detailed tracking:Construct taint propagation trailMore detailed metadata per application location PC of Instruction that tainted this location“tainted from” add

11、ressNot supported by previous lifeguard-specific HWInputViolationNewsome & Song05Flexible Hardware Acceleration for Instruction-Grain Program MonitoringShimin Chen8Instruction-Grain Lifeguard Metadata CharacteristicsOrganization variesper application byte/wordsize, format, semantics vary greatlyFreq

12、uently updatede.g., propagation trackingFrequently checkede.g., memory accessesFlexible Hardware Acceleration for Instruction-Grain Program MonitoringShimin Chen9Lifeguard Supportrare eventsRareUpdateCheckmetadata Event-capture and deliveryApplication (unmodified)Lifeguard (software)Event HandlersRa

13、re e.g., malloc/free, system callsFrequent e.g., memory access,data movementEventsGeneral-Purpose HW improving DBI Performance bottlenecks: metadata mapping, updates, and checks123Flexible Hardware Acceleration for Instruction-Grain Program MonitoringShimin Chen10Our Contributionsrare eventsRareUpda

14、teCheckmetadata Event-capture and deliveryApplication (unmodified)Lifeguard (software)Event HandlersRare e.g., malloc/free, system callsFrequent e.g., memory access,data movementEventsM-TLBIFITMetadata-TLBfor metadata mappingInheritance Trackingfor metadata updatesIdempotent Filtersfor metadata chec

15、ksFlexible Hardware Acceleration for Instruction-Grain Program MonitoringShimin Chen11OutlineIntroductionBackgroundThree Hardware Acceleration TechniquesMetadata-TLBInheritance TrackingIdempotent FiltersExperimental EvaluationConclusionFlexible Hardware Acceleration for Instruction-Grain Program Mon

16、itoringShimin Chen12Metadata-TLB: MotivationMetadata per app byte/wordElement size may varyTwo-level structure:Robustness & space efficiencyMapping: application address metadata addressFrequently used in almost every handlerCan be very costlymetadataLevel-1indexLevel-2 chunksFlexible Hardware Accele

17、ration for Instruction-Grain Program MonitoringShimin Chen13Example (TaintCheck) map *mp = level1_indexsrc_addr16; mov %eax, %ecx shr $16, %ecx mov level1_index(,%ecx,4),%ecx int idx = (src_addr & 0 xffff)2; and $0 xffff, %eax shr $2, %eax UChar mem_taint = mpidx; movzbl (%ecx,%eax,1), %eax reg_tain

18、tdest_reg |= mem_taint; or%al, reg_taint(%edx) nlba (); nlbavoid dest_reg_op_mem_4B (UINT32 src_addr /*%eax*/, UINT32 dest_reg /*%edx */) / app instruction type: dest_reg dest_reg op mem(src_addr) / handler operation: reg_taint(dest_reg)|= mem_taint(src_addr)Metadata Mapping takes 5 out of 8 instruc

19、tions !Flexible Hardware Acceleration for Instruction-Grain Program MonitoringShimin Chen14Our Solution: Metadata-TLBA TLB-like HW associative lookup tableLMA (Load Metadata Address) instruction:Application address lifeguard metadata addressManaged by (user-mode) lifeguard softwareFlexible Hardware

20、Acceleration for Instruction-Grain Program MonitoringShimin Chen15Example (TaintCheck) w/ M-TLB map *mp = level1_indexsrc_addr16; mov %eax, %ecx shr $16, %ecx mov level1_index(,%ecx,4),%ecx int idx = (src_addr & 0 xffff)2; and $0 xffff, %eax shr $2, %eax UChar mem_taint = mpidx; movzbl (%ecx,%eax,1)

21、, %eax reg_taintdest_reg |= mem_taint; or%al, reg_taint(%edx) nlba (); nlbavoid dest_reg_op_mem_4B (UINT32 src_addr /*%eax*/, UINT32 dest_reg /*%edx */) / app instruction type: dest_reg dest_reg op mem(src_addr) / handler operation: reg_taint(dest_reg)|= mem_taint(src_addr) UChar *p = LMA_macro(src_

22、addr); LMA %eax, %ecx UChar mem_taint = *p; mov (%ecx), %al reg_taintdest_reg |= mem_taint; or%al, reg_taint(%edx) nlba (); nlbaReduce handler size by half !Flexible Hardware Acceleration for Instruction-Grain Program MonitoringShimin Chen16Inheritance Tracking: MotivationPropagation tracking is exp

23、ensiveMetadata updates for almost every app instructionPrevious hardware solutions track propagationautomatically update metadata in hardwareProblem: only support simple metadata semanticse.g., do not support TaintCheck w/ detailed trackingOur goal: flexibility AND performanceIdea: inheritance struc

24、ture is common, so lets track inheritance in hardware!Flexible Hardware Acceleration for Instruction-Grain Program MonitoringShimin Chen17Problem with General Inheritance TrackingProblem: state explosion for binary operations !mov %eax Amov B %eaxtaint(%eax) = taint(A)taint(B) = taint(%eax)Applicati

25、onPropagation Tracking%eax inherits from AB inherits from %eaxInheritance Trackingadd %ebx Dtaint(%ebx) |= taint(D)insert D into %ebxs inherit-from listFlexible Hardware Acceleration for Instruction-Grain Program MonitoringShimin Chen18Unary Inheritance TrackingMany lifeguards can take advantage of

26、unary IT:MemCheckTaintCheckLarge performance improvements if usedCan be disabled if unary IT does not match the lifeguardcheckcheckknownFlexible Hardware Acceleration for Instruction-Grain Program MonitoringShimin Chen19Tracking Register InheritanceOriginal eventIT table for registersState Transitio

27、n& Event to DeliverDeliver eventIT(%rs)IT(%rd)Transformed eventMore details in the paper: IT table and state transition table details Conflict detectionFlexible Hardware Acceleration for Instruction-Grain Program MonitoringShimin Chen20Examplemem_to_regreg_to_memApplicationBefore mem_to_memInheritan

28、ce Trackingmem_to_regdest_reg_op_memreg_to_mem imm_to_memCan significantly reduce metadata update events!mov %eax Amov B %eaxmov %ebx Cadd %ebx Dmov E %ebxFlexible Hardware Acceleration for Instruction-Grain Program MonitoringShimin Chen21Idempotent Filters: IdeaTypically, metadata checks give the s

29、ame result ifEvent parameters are the same andMetadata are the sameIdea: filter out idempotent (redundant) eventsFor example:AddrCheck:After checking that a memory location is allocatedSubsequent loads/stores to the same location are safeUntil the next free() eventLockSet: (surprisingly)In between s

30、ynchronization events (e.g., lock/unlock)Check first load to a locationCheck first store to a locationFlexible Hardware Acceleration for Instruction-Grain Program MonitoringShimin Chen22OutlineIntroductionBackgroundThree Hardware Acceleration TechniquesExperimental EvaluationLog-Based Architectures

31、(LBA)Simulation Study (w/ reduced input sets)PIN-based Analysis (w/ full inputs)ConclusionFlexible Hardware Acceleration for Instruction-Grain Program MonitoringShimin Chen23Log-Based Architecturesrare eventsRareUpdateCheckmetadata Event-capture and deliveryApplication (unmodified)Lifeguard (softwar

32、e)Event HandlersRare e.g., malloc/free, system callsFrequent e.g., memory access,data movementEventsLog-Based Architecture (LBA)Flexible Hardware Acceleration for Instruction-Grain Program MonitoringShimin Chen24PPPPPPPPPPPPPPPPIdea: Exploiting Chip MultiprocessorsLBA componentsFlexible Hardware Acc

33、eleration for Instruction-Grain Program MonitoringShimin Chen25Simulation Setup: Dual-Core LBA SystemLog Transport(e.g. L2 cache)Core 1Core 2decompressCompress capturedispatchOperating System: Fedora Core 5Application LifeguardIT & IFM-TLBApplication and lifeguard are processesApplication is stalled

34、 when log buffer is fullModel a 2-level cache hierarchyExtend Virtutech SimicsFlexible Hardware Acceleration for Instruction-Grain Program MonitoringShimin Chen26Overall Performance: TaintCheck1.36XLBA baselineLBA optimizedSlowdown =application execution time w/o lifeguardapplication execution time

35、w/ lifeguardFlexible Hardware Acceleration for Instruction-Grain Program MonitoringShimin Chen27Applying Our Techniques One by OneAddrCheckTaintCheckTaintCheck w/ detailed trackingLockSetMemCheck3.231.901.027.806.053.813.273.362.291.364.212.711.500.01.02.03.04.05.06.07.08.09.010.0BASEMTL

36、BMTLB+IFBASEMTLBMTLB+ITMTLB+IT+IFBASEMTLBMTLB+ITBASEMTLBMTLB+ITBASEMTLBMTLB+IFaverage slowdownsIT, IF, and M-TLB are indeed complementaryAchieve dramatically better performanceFlexible Hardware Acceleration for Instruction-Grain Program MonitoringShimin Chen28PIN-Based Analysis: ITIT removes 35.8% to 82.0% of the propagation eventsFlexible Hardware Acceleration for Instruction-Grain Program MonitoringShimin Chen29PIN-Based Analysis: IF010203040506070808163264128256number