Machine-Level Programming IV: Data Sept. 20, 2006Basic Data TypesArray AllocationArray AccessArray ExampleArray Accessing ExampleReferencing ExamplesArray Loop ExampleArray Loop Implementation (IA32)Nested Array ExampleViewing as Multidimensional ArrayNested Array Row AccessNested Array Row Access CodeNested Array Element AccessNested Array Element Access CodeStrange Referencing ExamplesMulti-Level Array ExampleElement Access in Multi-Level ArrayArray Element AccessesSlide 20Using Nested ArraysDynamic Nested ArraysDynamic Array MultiplicationOptimizing Dynamic Array Mult.StructuresGenerating Pointer to Struct. MemberStructure Referencing (Cont.)AlignmentSpecific Cases of Alignment (IA32)Specific Cases of Alignment (x86-64)Satisfying Alignment with StructuresDifferent Alignment ConventionsOverall Alignment RequirementOrdering Elements Within StructureArrays of StructuresAccessing Element within ArraySatisfying Alignment within StructureUnion AllocationUsing Union to Access Bit PatternsByte Ordering RevisitedByte Ordering ExampleByte Ordering Example (Cont).Byte Ordering on IA32Byte Ordering on SunByte Ordering on x86-64Buffer Overflow AttacksString Library CodeVulnerable Buffer CodeBuffer Overflow ExecutionsBuffer Overflow Stack (IA32)Buffer Overflow Stack ExampleBuffer Overflow Example #1Buffer Overflow Stack Example #2Buffer Overflow Stack Example #3Malicious Use of Buffer OverflowExploits Based on Buffer OverflowsSummaryMachine-Level Programming IV:DataSept. 20, 2006Machine-Level Programming IV:DataSept. 20, 2006Structured DataStructured DataArraysStructsUnionsData/ControlData/ControlBuffer overflowclass07.ppt15-213“The course that gives CMU its Zip!”– 2 –15-213, F’06Basic Data TypesBasic Data TypesIntegralIntegralStored & operated on in general registersSigned vs. unsigned depends on instructions usedIntel GAS Bytes Cbyte b 1 [unsigned] charword w 2 [unsigned] shortdouble word l 4 [unsigned] intquad word q 8 [unsigned] long int (x86-64)Floating PointFloating PointStored & operated on in floating point registersIntel GAS Bytes CSingle s 4 floatDouble l 8 doubleExtended t 10/12/16 long double– 3 –15-213, F’06Array AllocationArray AllocationBasic PrincipleBasic PrincipleT A[L];Array of data type T and length LContiguously allocated region of L * sizeof(T) byteschar string[12];x x + 12int val[5];xx + 4 x + 8 x + 12 x + 16 x + 20double a[4];x + 32x + 24xx + 8 x + 16char *p[3];xx + 8 x + 16x + 24xx + 4 x + 8 x + 12IA32x86-64– 4 –15-213, F’06Array AccessArray AccessBasic PrincipleBasic PrincipleT A[L];Array of data type T and length LIdentifier A can be used as a pointer to array element 0Type T*ReferenceReferenceTypeTypeValueValueval[4] int 3val int * xval+1 int * x + 4&val[2] int * x + 8val[5] int ??*(val+1) int 5val + i int * x + 4 i1 5 2 1 3int val[5];xx + 4 x + 8 x + 12 x + 16 x + 20– 5 –15-213, F’06Array ExampleArray ExampleNotesNotesDeclaration “zip_dig cmu” equivalent to “int cmu[5]”Example arrays were allocated in successive 20 byte blocksNot guaranteed to happen in generaltypedef int zip_dig[5];zip_dig cmu = { 1, 5, 2, 1, 3 };zip_dig mit = { 0, 2, 1, 3, 9 };zip_dig ucb = { 9, 4, 7, 2, 0 };zip_dig cmu;1 5 2 1 316 20 24 28 32 36zip_dig mit;0 2 1 3 936 40 44 48 52 56zip_dig ucb;9 4 7 2 056 60 64 68 72 76– 6 –15-213, F’06Array Accessing ExampleArray Accessing ExampleIA32 Memory Reference CodeIA32 Memory Reference Codeint get_digit (zip_dig z, int dig){ return z[dig];} # %edx = z # %eax = digmovl (%edx,%eax,4),%eax # z[dig]ComputationComputationRegister %edx contains starting address of arrayRegister %eax contains array indexDesired digit at 4*%eax + %edxUse memory reference (%edx,%eax,4)– 7 –15-213, F’06Referencing ExamplesReferencing ExamplesCode Does Not Do Any Bounds Checking!Code Does Not Do Any Bounds Checking!ReferenceReferenceAddressAddressValueValueGuaranteed?Guaranteed?mit[3] 36 + 4* 3 = 48 3mit[5] 36 + 4* 5 = 56 9mit[-1] 36 + 4*-1 = 32 3cmu[15] 16 + 4*15 = 76 ?? Out of range behavior implementation-dependentNo guaranteed relative allocation of different arrays zip_dig cmu;1 5 2 1 316 20 24 28 32 36zip_dig mit;0 2 1 3 936 40 44 48 52 56zip_dig ucb;9 4 7 2 056 60 64 68 72 76YesYesNoNoNoNoNoNo– 8 –15-213, F’06int zd2int(zip_dig z){ int i; int zi = 0; for (i = 0; i < 5; i++) { zi = 10 * zi + z[i]; } return zi;}Array Loop ExampleArray Loop ExampleOriginal SourceOriginal Sourceint zd2int(zip_dig z){ int zi = 0; int *zend = z + 4; do { zi = 10 * zi + *z; z++; } while (z <= zend); return zi;}Transformed VersionTransformed VersionAs generated by GCCEliminate loop variable iConvert array code to pointer codeExpress in do-while formNo need to test at entrance– 9 –15-213, F’06# %ecx = zxorl %eax,%eax # zi = 0leal 16(%ecx),%ebx # zend = z+4.L59:leal (%eax,%eax,4),%edx # 5*zimovl (%ecx),%eax # *zaddl $4,%ecx # z++leal (%eax,%edx,2),%eax # zi = *z + 2*(5*zi)cmpl %ebx,%ecx # z : zendjle .L59 # if <= goto loopArray Loop Implementation (IA32)Array Loop Implementation (IA32)RegistersRegisters%ecx z%eax zi%ebx zendComputationsComputations 10*zi + *z implemented as *z + 2*(zi+4*zi) z++ increments by 4int zd2int(zip_dig z){ int zi = 0; int *zend = z + 4; do { zi = 10 * zi + *z; z++; } while(z <= zend); return zi;}# %ecx = zxorl %eax,%eax # zi = 0leal 16(%ecx),%ebx # zend = z+4.L59:leal (%eax,%eax,4),%edx # 5*zimovl (%ecx),%eax # *zaddl $4,%ecx # z++leal (%eax,%edx,2),%eax # zi = *z + 2*(5*zi)cmpl %ebx,%ecx # z : zendjle .L59 # if <= goto loopint zd2int(zip_dig z){ int zi = 0; int *zend = z + 4; do { zi = 10 * zi + *z; z++; } while(z <= zend); return zi;}# %ecx = zxorl %eax,%eax # zi = 0leal 16(%ecx),%ebx # zend = z+4.L59:leal (%eax,%eax,4),%edx # 5*zimovl (%ecx),%eax # *zaddl $4,%ecx # z++leal (%eax,%edx,2),%eax # zi = *z + 2*(5*zi)cmpl %ebx,%ecx # z : zendjle .L59 # if <= goto loopint zd2int(zip_dig z){ int zi = 0; int *zend = z + 4; do { zi = 10 * zi + *z; z++; } while(z <= zend); return zi;}# %ecx = zxorl %eax,%eax # zi = 0leal 16(%ecx),%ebx # zend = z+4.L59:leal (%eax,%eax,4),%edx # 5*zimovl (%ecx),%eax # *zaddl $4,%ecx # z++leal (%eax,%edx,2),%eax # zi = *z + 2*(5*zi)cmpl %ebx,%ecx # z : zendjle .L59 # if <= goto loopint zd2int(zip_dig z){ int zi = 0; int *zend = z + 4; do { zi = 10 * zi + *z; z++; } while(z <= zend); return zi;}# %ecx = zxorl %eax,%eax # zi = 0leal
View Full Document