### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Program and Data Representation CS 2150

UVA

GPA 3.71

### View Full Document

## 46

## 0

## Popular in Course

## Popular in ComputerScienence

This 95 page Class Notes was uploaded by Mrs. Carolyne Abbott on Monday September 21, 2015. The Class Notes belongs to CS 2150 at University of Virginia taught by David Evans in Fall. Since its upload, it has received 46 views. For similar materials see /class/209646/cs-2150-university-of-virginia in ComputerScienence at University of Virginia.

## Reviews for Program and Data Representation

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 09/21/15

Lecture 21 Calling Conventios 9 V httpwwwcsvirginiaeduc216 Calling Convention 0 Rules for how the caller and the callee make subroutine calls Caller needs to know How to pass parameters What registers might be bashed by called function What is state of stack after return Where to get result UVa C5216 Spring 2006 Lecture 21 Calling Conventions 3 Calling Convention Easiest for Caller Caller Callee 0 Where to put 0 Where to find params params What registers can I assume are same All of them Where to find result State of stack 0 What registers must I not bash None of them 0 Where to put result 0 State of stack UVa C5216 Spring 2006 Lecture 21 Calling Conventions 5 Menu X86 C Calling Convention 0 Java Byte Code Wizards UVa C5216 Spring 2006 Lecture 21 Calling Conventions Calling Convention Caller Callee 0 Where to put 0 Where to find params params What registers can I o What registers assume are same must I not bash Where to find result Where to put result State of stack State of stack UVa C5216 Spring 2006 Lecture 21 Calling Conventions X86 C Calling Convention CaHer CaHee o Params on stack in 0 Find params on stack in reverse order Must not bash EBX EDI or ESI Put res It in EAX Stack ru 5 next reverse order 0 Can assume EBX EDI and ESI are same 0 Find result 39n EAX o Stack rules ext Need to save and restore EAX ECX EDX Need to and restore EDI and ESI UVa C5216 Spring 2006 Lecture 21 Calling Conventions 6 saved ESI saved EDI local variable 3 ESP Stack Convention EBP Base Pointer Reference point for finding local variables and parameters local variable 2 Manipulated only explicitly local vanable 1 ebp4 ESP Stack Pointer HJMOJD was saved EBP Pointer to last element used on the stack return address oThe next free element is at esp4 9 EBP Manipulated implicitly by many E Paramenerl ebp8 instructions push pop call ret 3 parameer ebp12 u u IDo we need both of these a Parame Er3 abpl s w 52 5m 2 22quot 2 an mm 7 w 52 5mg 2 22quot 2 an mm a saved ESI ESP 3 saved EDI Maintaining EBP n 3 local variable 3 Ir Whlch g I I bl 2 dlreCtlon I Callee prologue oca vana e ShOUld the StaCk Must save old value of EBP push ebp local Vanable 1 QrOW Update EBP to point to the new frame I saved EBP If rst local mov EBP ESR Lg return address variable Use EBP to find parameters ebp8 g 1 ebp12 te E parame r int an Callee before returning paramelerz What is Restore old value of EBP pop ebp In parameter 3 an m 52 5m 2 22quot 2 an mm 9 w 52 5mg 2 22quot 2 an Wm u Maintaining ESP Caller Rules Caller it is maintained implicitly if Caller Before Caller After parameters are pushe 1 Save bashable 2 Restore bashable Callee prologue Eezaiggr393 ulse reg39Sters Need to make enough space for local 239 Push parameters 139 Remove variables t k on 5 35 parameters from suh esP pace neededgt 3 call ltroutinegt stack Callee before return implicit push 51p Deallocate local variables from stack 0 5p ebp 39 mustbe abne befole pop ebp w 52 5m 2 22quot 2 an Wm w 52 5mg 2 22quot 2 an mm 2 Callee Rules 0 Callee Prologue 0 Callee Return 5 ret 1 Save EBP 4 Restore EBP 2 Update EBP 3 Allocate local 3 Deallocate local variables ESP variables ESP 4 Save calleesave 2 Restore calee registers we use save registers EBX EDI E51 1 Leave return value in EAX IWhich of the callee prologue steps could be done by caller I To work with library code compiler generated code must follow all rules carefully If you don t care about this which rules must you follow UVa C5216 Spring 2006 Lecture 21 Calling Conventions 13 UVa C5216 Spring 2006 Lecture 21 Calling Conventions 14 Byte Code Wizardry Awards Mysteryjava 0 Implementation of SHAl cryptographic hash algorithm Code posted on CS216 website now private static int obfuscateint num int cnt int a num int b cnt for inti 0 i lt 216 i 3 bbaibbb if b 0 return num ese forinti 0 i lt 256 ia a1 return a UVa C5216 Spring 2006 Lecture 21 Calling Conventions 15 UVa C5216 Spring 2006 Lecture 21 Calling Conventions 16 Black Hat Honorable Mentions Call the Testergenerate method Richard Hsu Dan Chen 244 Michael Thomas Billy Chantree 244 Mike Liu 316 Jongmin Kim 380 Fastest Code 0 Not enough variance to distinguish o Effectively tied for fastest Bin Zhou Mark Mitchell Bijan Vakili David Trang Jake Fowler and Sean Talts Michael Thomas and Billy Chantree Eric Bradbury and Robert Yip UVa C5216 Spring 2006 Lecture 21 Calling Conventions 17 UVa C5216 Spring 2006 Lecture 21 Calling Conventions 18 Lecture 3 23 2 Review quot Fast Dictionaries quot httpwwwcsvirginiaeduc5216 Exam 2 Review Questions 0 JVML Do istore1 and astore1 share the same memory location 0 Memory management Explain memory leaks 0 Complexity classes What is NP Complete UVa CS216 Spring 2006 Lecture 23 Fast Dictionaries 3 Announcements 0 PS7 Comments will be posted later today 0 Exam 2 will be posted Thursday after 5pm 0 Office hours Today 23pm Tomorrow 10 11am 0 After Thursday I will start charging storage fees on uncollected graded assignments Exam 1 1 point per page per day Problem Sets 1 star color per week UVa CS216 Spring 2006 Lecture 23 Fast Dictionaries 2 C8216 Roadmap Data Representation Program Representation Rest of C5216 Real World Problems He39 Objects Pythc E33133 H i Arrays Code LOW level Ox42381a Addresses C code language ssilegfgglt engogafgtle rest S JVML E g acmne 0 fJSkmaESEZtt39 Q ll E E39E l 35 m Assembly another assembly language RISC V Iul VVUI Iu I UVa CS216 Spring 2006 Lecture 23 Fast Dictionaries 4 Fast Dictionaries 0 Problem set 2 question 5 You may assume Python s dictionary type provides lookup and insert operations that have running times in 01quot 0 Class 6 fastest possible search using binary comparator is 0log n ICan Python really have an 01 lookup Fast Dictionaries Data Representation o If the keys can be anything No best one comparison can Hello Objects do is eliminate H i 0 lt Arrays 12 the elements 0x42381a 4 I X The keys must UVa CS216 Spring 2006 Lecture 23 Fast Dictionaries 5 be bltS SO we 01001010 Bits can do better UVa CS216 Spring 2006 Lecture 23 Fast Dictionaries 6 Table Works greatunless the key space is sparse w csm smg 2m 7 mm 2 FasQDlzonnangs 7 Sparse Lookup Table Keys names words of up to 40 7 bit ASCII characters How big a table do we need 40 7 280 2230 191034 entries We need lookup tables where many keys can map to the same entry o Hash Function h Key gt 0 ml H ere h firstLetterKey w csm smg 2m 7 mm 2 FasQDlzonnangs Collisions What if we need both Colleen and Cathy keys w csm smg 2m 7 mm 2 FasQDlzonnangs Separate Chaining 0 Each element in hash table is not a ltkey valuegt pair but a list of pairs uvacszm SDnnann rlezhneza FasQDlzonnangs 11 Hash Table Analysis Lookup Running Time Worst Case N N entries all in same bucket Hopeful Case 01 Most buckets with lt 6 entries w csm smg 2m 7 mm 2 FasQDlzonnangs Requirements for Hopeful Case Function h is well distributed for key space for a randomly selected k e K probability Mk i 1m Size of table m scales linearly with N Expected bucket size is Nm Finding a good h can be tough more next class w csm smg 2m 7 mm 2 FasQDlzonnangs 13 Saving Memory Can we avo the overhead of all those linked sts w csm smg 2m 7 mm 2 FasQDlzonnangs 14 Linear Open Addressing w csm smg 2m 7 mm 2 FasQDlzonnangs 15 Sequential Open Addressing def lookup T k i hash k while not looped all the way around if Ti null return null else if Tikey return Tivaue else i i 1 mod Tength w csm smg 2m 7 mm 2 FasQDlzonnangs 15 Problems with Sequential Primary Clustering Once there is a full chunk of the table anything hash in that chunk makes it grow Note that this happens even if h is well distributed Improved strategy Don t look for slots sequentially i i 5 mod Tength Doesn t help just makes clusters appear scattered w csm smg 2m 7 m m 17 Double Hashing Use a second hash function to look for slots i i hash2 K mod Tength Desirable properties of hash2 Should eventually try all slots result of hash2K should be relatively prime to m Easiest to make m prime Should be independent from hash w csm smg 2m 7 mm 2 FasQDlzonnangs IE Lecture 5 Logs and Trees httpwwwcsvirginiaeducs216 MIXes Encrypted Votes Decrypted Votes 4 Ra nc om secret permutation UVa C5216 Spring 2006 Lecture 5 Logs and Trees 3 PublicKey Cryptography 0 Private procedure E 0 Public procedure D o Identity E D m D E m m 0 Secure cannot determine E from D 0 Concept stated by Whitfield Diffie and Martin Hellman in 1976 but didn t know how to find suitable E and D UVa C5216 Spring 2006 Lecture 5 Logs and Trees 5 Menu 0 Ron Rivest s talk Mixnets and voting Publickey cryptography dynamic programming 0 Trees 0 PS1 Grading UVa C5216 Spring 2006 Lecture 5 Logs and Trees Security Properties 1 Voters must be able to create votes but not decrypt them 2 Observer should be able to verify that output votes correspond to input votes but not match up votes UVa C5216 Spring 2006 Lecture 5 Logs and Trees 4 RSA The era of electronic mail Potter1977 may soon be upon us we must ensure that two important properties of the current paper mail system are preserved a messages are private and b messages can be signed R Rivest A Shamir and L Adleman A Method for Obtaining Digital Signatures and PublicKey Cryptosystems Jan 1978 UVa C5216 Spring 2006 Lecture 5 Logs and Trees 6 We will not attempt to explain why it works and is probably secure in C8216 See links to paper and slides Pu blic P 8 6L PRiME e n c ry pti o n fu nction l P r i V a HSA39 ruaucm CHVFTOSYSTEM us PATENTMMEAZS e n c ry ptio n fu n Ctio n IT S 405139 AN ALGORiTHM UVa C5216 Spring 2006 Lecture 5 Logs and Trees 7 Resu File quotCcle6worksoaceDSZRSADvquot line 17 in RSAencrypt return M RSAencrypt M e 1 n n File quotCcle6worksoaceDSZRSADvquot line 17 in RSAencrypt return M RSAencrypt M e 1 n n File quotCcle6worksoaceDSZRSADvquot line 17 in RSAencrypt return M RSAencrypt M e 1 n n RuntimeError maximum recursion depth exceeded UVa C5216 Spring 2006 Lecture 5 Logs and Trees 9 Implementing RSA def RSAencrypt MC If e ZOOdigit number return 1 else return M RSAencrypt M e 1 n n Note this actually works in Python even though RSA needs 100digit values but not in Java because integers are not limited to a fixed size We ll consider number representations later in the class UVa C5216 Spring 2006 Lecture 5 Logs and Trees 8 Analyzing RSA def RSAencrypt M e n ife 0 return 1 else return M RSAencrypt M e 1 n n How many recursive calls The value of the e parameter scales as C26 size of e Can we use dynamic programming and math to make this faster UVa C5216 Spring 2006 Lecture 5 Logs and Trees 10 Fast Exponentiation a9aaaaaaaa Multiplication is associative Fast Exponentiation def square x return x x def RSAencrypt M e n if e 0 return 1 elife 2 return squareRSAencrypt M e2 n n else return M RSAencrypt M e 1 n n UVa C5216 Spring 2006 Lecture 5 Logs and Trees 11 UVa C5216 Spring 2006 Lecture 5 Logs and Trees 12 Analysis 219 defsquare x retum x x def RSAencrypt M e n i 5 elife 2 0 return squareRSAencrypt M e2 n n else return M RSAencrypt M e 1 n n How many recursive calls Worst case e2771 a 2 calls E logz e 3 a return 1 339 w smswm mus 7 mm 5 my And 3971 Changing Bases x bkng logux 10g 1 ng quot logax loga b X loga 10gb x 1 log blog x X log x 10gb x logaxloga b So within 0 9 Q the base doesn t matter VzESZISSvnuq mam may an 15 Implementing RSA a9 defsquare x retum x x def RSAencrypt M e n 3 Ife return 1 a 339 elife 0 return squareRSAencrypt M e2 n n 4 else a return M RSAencrypt M e 1 n n Recursive calls 6 910g2 e 32 Running time 6 910g2 e if multiplication time is 01 Note that this cannot really be true w smswm mus 7 mm 5 m And 3971 a 17 Logarith ms Review Logarithm is inverse of exponential x 10gb bx 71 ng Bases Is logz x e O 10g3 x Is logz x e Q 10g3 x w smswm mus 7 mm 5 my And 3971 Logs and Trees Many tree algorithms have running time e logN where N is the number of nodes in the tree since for a well balanced tree N bh1 1 h 10gbN w smswm mus 7 mm 5 my And 3971 Public Key Applications Privacy Alice 30b Plaintext EncnlptclpherteXt Decrypt Plaintext l Bob39s PUbliC Key Bob39s Private Key Alice encrypts message to Bob using Bob s Private Key Only Bob knows Bob s Private Key 2 only Bob can decrypt message w smswm was 7 mm 5 m And 3971 Signatures B b Alice Signed o Plaintext Message Plaintext l Alice s Private Key Alice s Public Key 0 Bob knows it was from Alice since only Alice knows Alice s Private Key 0 Nonrepudiation Alice can t deny signing message except by claiming her key was stolen o Integrity Bob can t change message oesn t know Alice s Private Key mamas mam moguan 19 Encrypted MIXes Random secret Votes value picked by C1 EKUM Kerryquot VOter M ft part of EKRMC g om secret permutation Mux keys KUM KRM mamas mam moguan 21 Voting Application Orange Republicrat Democrican Party Party C EKUG Badnarik R1 Does publishing R1 help mamas mam Snugnib 2a MIXes C1 EKUM Kerry M E nc ry pted vetes Decrypted Votes Oppsdoesn tIworkv anyone can39use public keylt39o computefEKUM M1 for outputs and compare to inputs mamas mam moguan 2n Voting Application Republicrat Democrican Orange Party Party Pa rty C EKUR EKUD EKUG Badnarik R1 R2 R3 Each mux decwpts with private key and removes R mamas mam moguan 22 Auditin Muxes Republicrat Democrican Orange Party Party Party quotWW EKUR EKUD EKUG V R1 R2 R3 OWPWJ EKUD EKUG V R1 R2 IfR revealsj and R3 D can check EKUR Outputl IIR3 Inputl 1 mamas mam Snugnib 24 Catching Cheaters Probability a mux can cheats on k votes without getting caught 1216 Probability a voters vote is revealed to eavesdropper m muxes Note unaudited votes only be 12 one of nZ possible outputs If muxes collude all bets are off w smswm mus 7 mm 5 my 2nd Yves Trees w smswm mus 7 mm 5 my 2nd Yves Calculating Height I Height of a Node def height self length of the If selfsLeaf longest path from return 0 that node to a else leaf return 1 maxselfgetLeftChildheight selfgetRightChildheight w smswm was 7 mm 5 m 2nd Yves Voting Caveat Real problems with voting have very little to do with cryptography or mixes w smswm mus 7 mm 5 my 2nd Yves Tree Node Operations getLeftChild Node getRightChild Node getInfo Node def isLeaf self return selfgetLeftChild None and selfgetRightChild None w smswm mus 7 mm 5 my 2nd Yves Analyzing Height What is the asymptotic running time or our height procedure def height self if self isLeaf 0 return 0 else return 1 maxselfgetLeftChildheight selfgetRightChiIdheight w smswm was 7 mm 5 m 2nd Yves Tree Preorder Traversal mamas mam mayan a Preorder Traversal clef preorder t print tinfo for c in tchidren cpreorder N is number of nodes in t Running time N Space use worst case 0 well balanced case 010gN mamas mam mayan 32 PSl Returned in section today mamas mam mayan 33 C8216 PS Grading Scale Gold Star Excellent Work You got everything I wanted on this PS Green Star Better than good work Blue Star Good Work You got most things on this PS but some answers could be better Silver Star Some problems Make sure you understand the comments Red Star Serious problems and lack of effort PSl Average 139 mamas mam mayan a4 No upper limit 4 139 Double Gold Star exceptional work Better than I expected anyone would do i t Triple Gold Star Better than I thought possible Quadruple Gold Star You have broken important new ground in CS which should be published in a majorjournal eg invented a alignment algorithm better than BLAST Quintuple Gold Star You deserve a Turing Award find an 0nk solution to finding optimal phylogenies mamas mam suman 35 Philosophy This generation of students got into Harvard by doing exactly and precisely what teacher wants If teacher is vague about what he sic wants they work a lot harder to figure out what they want and whether or not it is good The vaguer the directions the more likely the opportunity for serendipity to happen It drives them nutsl Harvard Professor John Stilgoe on 60 Minutes 4 January 2004 mamas mam suman as Lecture 18 Code Safety and Virtual Machines Duke SulcldE Picture by Gary McGraW httpwwwcsvirginiaeduc5216 How to get more than 256 local variables wide ltopcodegt ltbyte1gt ltbyte2gt Opcode is one of iload oad aload Iload dload istore fstore astore Istore dstore or ret Modi es instruction to take 2 byte operand byte1 ltlt 8 byte2 w csm smg 2m 7 mm 11 End safety Method Calls invokestatic ltmethodgt Invokes a static class method ltmethodgt on the parameters on the top of the stack Finds the appropriate method at run time based on the actual type of the this object w csm smg 2m 7 mm 11 End safety JVML Instruction Set 205 out of 256 possible opcodes used w csm smg 2m 7 mm 11 End safety 2 Method Calls invokevirtual ltmethodgt Invokes the method ltmethodgt on the parameters and object on the top of the Finds the appropriate method at runtime based on the actual type of the this object invokevirmal ltMethod void pnntlnjavaangStn39nggt w csm smg 2m 7 mm 11 End safety Example public class Sample1 static public void main String args Systemerrprintln quotHellolquot Systemegtltit 1 w csm smg 2m 7 mm 11 End safety public dass Samplel static public void main String args l tem err prindn Hellolquot 5V3 gt Javap c Samplel Mtemegt1y Compiled from Sample1java public class Samplel exmnds javalang0bject pu lic Samplel public smuc void mainiavalangsuing Melhod Sampleio aioa l invokespecial n1 ltMethod javalang0bjetgt 4 ie H Method void mainiavalangsmng o getsbatic 32 39 ioprinstream errgt 3 ldc 33 ltString quotHelloquotgt 5 invokevirtual 34 ltMed10d void printlniavalangsuinggt s iconst1 9 invokeslatic 35 ltMed10d void exitintgt 12 return n uv csm span was r lezmre 11 End ssrety 7 Method void mainjavalangString 0 aload70 1 39DDnSLO public class Cast 2 aaload smuc public void main String args 3 astoreil iec 4 geetauc 32 ltFleld Java X Oblect argsip H 7 new 3 5551 Jang svstem out prindn result Smi lg x 10 up 11lhvolltespeclal 34 ltMeth 14 ldc 35 lt5U ll lg result 15 lrlvokevlrmal 35 Method Java larg stingsurrer appendOava lang smrggt 19 aloadil 20 checkcast 7 ltClass javalang5ringgt 23 lrlvokevlrmal 35 entirudimimgam urmwmdrimuncaring 25 lrlvokevlrmal 38 ltMeihod Java lang Sml39lg toStIlrlggt 29 lrlvokevlrmal 39 ltM21hodvold Uln nUava lam suing turn w c5216 sum 2m 71mm 11 code has a Theiworgicigstryicinn Jsr branchbvte1 branchbvte2 Forms Jsr 168 0X58 operand Stack address scr pt The address or the opcode or the instruction immediatelv toll OWii lg this Jsr instruction is pushed onto the operand stack as a value or tvpe ess n an v a nchby thistr instruction The target address must be that otan opcode or an lrlstructlorl Within the method that contains thlsjsr ll39lstructlol39l Notes The Jsr instruction is used With the rat instruction in the irnplernenta or the llnally clauses or the Java programming langua e Note thath pushes the address onto the operand stack and ret gets it out or a local variable This asvmmetrv is intentional ti on r uv csm spans 2m 7 lezmre 11 End ssrety Cast Instruction public class Cast static public void main String args 39 ct x39 r x Object args0 Systemoutprintln quotresult Stn39ng x uv csm span was r lezmre 11 End ssrety JVML Instruction Set 205 out of 256 possible opcodes used uv csm spans 2m 7 lezmre 11 End ssrety 1n Try Catch Finally public class JSR static public void main String args Systemoutprintnquotheoquot catch Exception e 5 st moutprintln quotThere was an exceptionquot finally Systemoutprintln quotI am finally herequot uv csm spans 2m 7 lezmre 11 End ssrety Method void mainava larig StringU Diblidass91 o getstatic 42 ltFieid 1a a lO PrintStrea MEWH WW WG WMSUN 3 ldc 3 ltStririg hello gt lamaquot Mpmmwmi 5 invokevirtual 4 ltlVlethod void printlri ratrMExcepnuneH 8 Jsr 35 SVStEn mtgin n Extw ml miiyr 11 9 46 SystEn cutpin n 1 am nally ltFielltl java lO Friantrea ldr lt5quotng There Mm an excepii 2o irivokevii39tual 4 ltlVlethcd m3 739 7 3 ml uni 33 aioad 2 Exception table from m target type 35 astore73 0 8 ltClassiaya larva ExceDtiDrD 36 getstatic 2 ltField Javal 0 11 29 any 39 idcw ltStririg i m final 14 26 29 any 41 invokevirtual 44 ltlVletho 29 33 29 any 44 ret 46 return JavaTM Programming Language compared 1390 C not 1390 C sorlf of A simple objectoriented distributed interpreted robust architecture neutral porta e highperformance multithreaded and dynamic language Sun95 Java int is 32 bits C int is gt 16 bits w csm smg 2m 7 mm 11 code Safety 13 w csm smg 2m 7 mm 11 code Safety 14 What is a secure programming language Language is designed so it cannot express certain computations considered insecure A few attempt to do this PLAN packet filters 2 Language is designed so that accidental program bugs are m likely to be caught by the compiler or run time environment instead of leading to security vulnerabilities H Safe Programming Languages 0 Type Safety Compiler and runtime environment ensure that bits are treated as the type they represent 0 Memory Safety Compiler and runtime environment ensure that program cannot access memory outside defined storage 0 Control Flow Safety Can tjump to arbitrary addresses Which of these does CC have Is Java the first language to have them No way LISP had them all in 1960 w csm smg 2m 7 mm 11 code Safety 15 w csm smg 2m 7 mm 11 code Safety 15 JavaTM Safety Type Safety Most types checked statically Coercions array assignments type checked at run time Memory Safety No direct memory access eg pointers Primitive array type with mandatory run time bounds chec i Control Flow Safety Structured control flow no arbitrary jumps Malicious Code Can a safe programming language protect you from 5 malcode H Code your servers in it to protect from buffer over ow bugs Only allow programs from untrustworthy origins to run if the are programmed in the safe language N w csm smg 2m 7 mm 11 code Safety 17 w csm smg 2m 7 mm 11 code Safety IE Safe Languages But how can you tell program was written in the safe language Get the source code and compile it most vendors and all malicious attackers refuse to provide source co e Specia compilation service cryptographically signs object files generated from the safe language SPIN Bershad96 Verify object files preserve safety properties of source language Java quot uv csm Spnng 2m 7 tenure 11 End Safety 19 Does JVML satisfy Javam s safety properties iconst2 push integer constant 2 on stack istore0 store top ofstack in variable 0 as int aload0 load object referencefrom variable 0 No This code violates Javam s type rules dim code java codeclass Java JVML Object Code JavaVM V User Wants to know JVML code satisfies Javaw39s safety properties uv csm Spnng 2m 7 tenure 11 End Safety 2 Java Security Architecture Verify Exception Security exception uv csm Spnng 2m 7 tenure 11 End Safety 21 uv csm Spnng 2m 7 tenure 11 End Safety 22 Mistyped Code method public static mainLjavaangStringV iconst2 gt java Simple IStor Lo Exception in thread aload0 quotmainquot ECOHSLZ javaangVerinynor ECOHSL3 class Simple method la main s39gnamre LjavaIangStringV end method R gister 0 contains wrong type Veri er error before any code runs uv csm Spnng 2m 7 tenure 11 End Safety 23 Runtime Error publicclass Cast tlc public void main String args ObleCtO quot9W Obie 0 Memod void mainjavalangSlIing 5mg 5 0 new 22 ltClass javalang0bjectgt s String 0 3 dup SY eTWtpmtm 4 invokeqaecial 21 ltMed10d 39quot39 javalang0bjectgt asmreJ s aloadJ 9 checkcast 23 ltClass iavaiangsmnggt 12 asmre 13 gematic 24 ltField iavaiopnnisueam outgt 1o aload 17 invokevirtual 25 ltMed10d void printlnuavaIangsuinggt return vv ism smv 2m e um in cm sum 24 Lecture 12 Automating Memory Management Garbage Collectors COAX Seoul 18 June 2002 Menu Stack and Heap 0 Mark and Sweep Stop and Copy 0 Reference Counting Java s Garbage Collector o Python s Solution httpwwwcsvirginiaeduc5216 UVa C5216 Spring 2006 Lecture 12 Automating Memory Management 2 Stack and Heap Review Stack Heap public class Strings public static void test A39StringBuffer sb new StringBuffer quothelloquot IB gt 39 39 39 39 39 Sb 39ava Ian Strin Buffe static public v0Id main String args JA 9 9 tsst o 3t5t O When do the stack and heap look like this UVa C5216 Spring 2006 Lecture 12 Automating Memory Management 3 Stack and Heap Review Stack Heap public class Strings public static void test StringBuffer sb new StringBuffer IB hello static public void main String args Sb QfValangStringBU e 2 test 0 test 0 UVa C5216 Spring 2006 Lecture 12 Automating Memory Management 4 Garbage Heap Stack Heap public class Strings public static void test StringBuffer sb new StringBuffer quothelloquot static public void main String args while true test 0 UVa C5216 Spring 2006 Lecture 12 Automating Memory Management 5 Garbage Collection 0 System needs to reclaim storage on the heap used by garbage objects 0 How can it identify garbage objects 0 How come we don t need to garbage collect the stack UVa C5216 Spring 2006 Lecture 12 Automating Memory Management 6 Mark and Sweep UVa c5215 Spring 2005 Lecture 12 Automating Memory Management Mark and Sweep John McCarthy 1960 first LISP implementation 0 Start with a set of root references 0 Mark every object you can reach from those references Sweep up the unmarked objects What are the root references References on the stack UVa c5215 Spring 2005 Lecture 12 Automating Memory Management W emit a mom 1 may 1 E w a enmwommmammit 11663 lt Q 9133 UVa c5215 Spring 2mm Lecture 12 Automating Memory Management After elsadd 5 Bottom of Stack String args root Species Duck 55 SpeciesSet CATAG Species this Goat Wm qu 5 Species of i Elf CGGTG CGATG Bottom of Stack String args root Species Duck 55 SpeciesSet CATAG uiew39Aua oqu urrent Species this Goat 5 Species CAGTG39 Top of Elf CGGTG CGATG SpeciesSetinsert returns Stack Bottom of Stack String args root Species Duck 55 SpeciesSet CATAG Species this Goat Wm qu 5 Species CAGTG39 of Elf CGGTG CGATG a g u lELu39AuabolALId in publ l P a wait th ek Push Jamequot hidu sit FH HSH while loop u lELu39AuabolALId U o urrerit Species Top of rib mama a small publ cl Garbage Collection torn of String args root Specles ssi SpecleSSet Top or t l may i aawaail apaaiewaaetrw prbltf39 rm may 0 u lELu39AuabolAqd U o Garbage Collect ori u lELu39AuabolAqd U o Top or In tialiZe Mark and Swee e Garbage Collection Stack tom of Strith args root Specles 0 ss SpecleSSet Top or t l actlve all objecE on stack while activei Empty 0 mm live foreach object a in active mark a as reachable nohagarbage foreach object 0 that a pain to ifo is not mar e hewactive hewactive u o active u lELu39AuabolALId ac Garbage Collect ori Bottom of Stack u ss Top or Stack Iv while a wm foreac active i E Garbage Collection Stack Bottom of Stack 1 String args lt i 8 root Species 9 v 3 i lt ss SpeciesSet a Top or Stack active ll objecE on stack while activei Empty 0 live foreach object a in active mark a as reachable hon arb foreach object 0 that a poinE if 0 is not marked hewactive hewactive u i o E age to active u Garbage Collect Ol l Stack Bottom of Stack Strihg args o lt 8 root Species m i lt ssi SpeciesSet a Top of Stack active all objects on stack while lac veiimpty 0 a ivt foreach Object a in active s reachable nonrgarbage foreach Object o that a Join to if 0 is not E E 2 7 m mar e wactive newac ve u o fictive i r Garbage Collect ori Stack Bottom of Stack gt i Strihg args root Species u Em39AuaboIAqd ss SpeciesSet Top or Stack ac39t39ive all objecE oh slack while lactiv II rim foreach Object a in active i eac a e foreach Object o ihata points to ifo is not mar e wactive newactive u o E 2 7 m m Ill active it sweep remove unmarked objects o Garbage Collect Ol l Stack Bottwobc w active all objecE on slack while lactiveisEmpty 0 M iv foreach Object a in active mark a as reachable Object o that a points to s not marked i n wactive newactive u o foreac i 0 active r a sweep remove unmarked objecis on heap u Garbage Collection Stack Bottom of Stack 1 Strihg args lt 8 root Species m i lt ssi SpeciesSet a Top of Stack active all objects on stack while lac veiimpty 0 a ivt foreach Object a in active s reachable nonrgarbage foreach Object o that a Join to if 0 is not E E 2 7 m mar e wactive newac ve u o fictive i r After mairi returns Stack Bottom Olt 5 String args 8 root Species 3 g lt ss SpeciesSet a Top or r l ac39t39ive all objecE oh slack while lactiv II rim foreach Object a in active eac a e foreach Object o ihata points to ifo is not mar e wactive newactive u o E 2 7 m m Ill active it sweep remove unmarked objects o Problems with Mark and Sweep Fragmentation free space and alive objects will be mixed Harder to allocate space for new objects Poor locality means bad memory performance 0 Caches make it quick to load nearby memow Multiple Threads One stack per thread one heap shared by all threads All threads must stop for garbage collection uv csm spans 2m 7 lecture 12 Mmmahng Mamary Management Stop and Copy Solves fragmentation problem Copy all reachable objects to a new memory area Alter copying reclaim the whole old heap Disadvantages More complicated need to change stack and internal object pointers to new heap Need to save enough memory to copy Expensive if most objects are not garbage uv csm sormg 2m r tenure 12 Mmmahng Memory Menegemem 25 Java s Garbage Collector Sun implementation Mark and Sweep collector Before collecting an object it will call nalize protected void finalize throws Throwable Can call garbage collector directly Systemgc uv csm sormg 2m r tenure 12 Mmmahng Memory Menegemem 27 Generational Collectors 0 Observation Many objects are shortlived Temporary objects that get garbage collected right away Other objects are longlived Data that lives for the durau39on of execution 0 Separate storage into regions Short term collect frequently Long term collect infrequently 0 Stop and copy but move copies into longerlived areas uv csm sormg 2m r tenure 12 Mmmahng Memory Menegemem 2s Reference Counting What if each object kept track of the number of references to it If an object has zero references it is garbage uv csm sormg 2m r tenure 12 Mmmahng Memory Menegemem 2a Referencing Counting T x new T 0 The x object has one reference Y X The object x references has 1 more ref The object ypre references has 1 less ref Leave scope where x is declared The object x references has 1 less ref uv csm sormg 2m r tenure 12 Mmmahng Memory Menegemem 2g Reference Counting class Recycle privam String name private Vector pals public Recycle String name lsna name pals new Vector o public void addPal Recycle r pals addElement r public class Garbage static public void main String args Recycle alice new Recycle quotalicequot ecyc ob new Recycle quotbobquot bobaddPal alice a Ice new Recycle coleen ob new Recycle quotdavequot uv csm sormg 2m r tenure 12 Mmmahng Memory Menegemem an Reference Counting class Recycle privam strin name private Vector pals public Recycle String name misname name pals new Vector t public void addPal Recycle r palsaddElement r public class Garbage static public void main string args Recyc e alice new Recycle quotalic ecy new R bobaddPal alice alice new Recycle quotcoleen bob new Recycle quotdavequot uy csm some 2m r tenure 12 Moomsmrg Memory Monogemem a Python s Implementation Automatic reference counting to manage objects but optional additional garbage collector we ll see why soon uy csm some 2m r tenure 12 Moomsmrg Memory Mogeme 33 Reference Counting class Recycle privam strin name private Vector pals public Recycle String name misname name pals new Vector t public void addPal Recycle r pals addElement r public class Garbage static public void main string args Recyc e alice new Recycle quotalic ec new R bobaddPal alice alice new Recycle quotcoleenquot b new Recycle quotdavequot uy csm some 2m r tenure 12 Moomsmrg Memory Monogemem 32 stat C ll lt appttpytistobiect self PyObJect y Pyssizet n PVustJSET lZHself assert y NULL it n W lNTJWAXM PyErr esmngtpy xcpyer owError cannot add more obiece to list return r1 it listJesizetselt n1 r1 return r1 PLINCREFW PyLisLSELITEWselt n v return 0 l ivy csm soooo zoos r rerooe 2 memooo Memory Msmoeme 34 Python Objects tdetine PyuewReterenceop 0m I have opgtobrefcnt 1 lemme 50quot debugging macros Jtdefine PyINCREFop quot0m mesa opgtobrefcnt Jtdefine PyDECREFop if opgtobrefcnt o PyCHECKREFCNTop else PyDeallocPy0bject op Jtdefine PyCHECK EFCNT0P if OPrgtobretcnt lt 0 iPyiNegativeRefcountiFILEi iLIN E7 PVObiect 0P uy csm some 2m r tenure 12 Moomsmrg Memory Monogemem 35 llstdealloc static void listideallocPyLlleblecl opl P SSl ll V 2e i PyObleclieciUnTrackwp P TRASHCANisAFEiElEGlep il oprsobgitem i N L l Do it backwems tor onristian Tl39smer There s a simple testcase nere somenow tnis reduces tnrasring wnen a 39Ver39 large list is created and immediately deleted l e oprgto sizei while quotl gt on Pygxogcngrtoprsobgtemiilt l PyMemfREHopeobilleWil il numjreeillsls lt MAXFREELlSTS m PyLlsLCneckExacuopD lreeillSlsnumjreeillsls e opt else oprgtob7lypergtlpilreePyOblec1 opy PyjriASHCAN ArgENDtop l uy csm some 2m r tenure 12 Moomsmrg Memory Monogemem as Lecture 1 Introduction Menu Motivating Problem 0 Course Structure Expectations Goals 0 Analyzing Algorithms UVa C5216 Spring 2006 Lecture 1 Analyzing Algorithms 2 Phylogeny if H g 1 g l a from httpwwwshefacuklanguagequantling in ll Hapanal 4 UVa C5216 Spring 2006 Lecture 1 Analyzing Algorithms Latin arboor domus casa Phylogeny arbre maison arbore casa arbolcasa albero casa tre hus strom domovni baum haus treow hus tree house UVa C5216 Spring 2006 Lecture 1 Analyzing Algorithms 4 Language Phylogeny French Romanian Spanih Italian Norwegian Czech German AngloSaxon EngHsh UVa C5216 Spring 2006 Lecture 1 Analyzing Algorithms Glirea Tree of Life Edentatta will lllti llrll39iw il nil l2 ll ll l l39klllltl i i Pholidota l g sill lwla ililrw LEngTlDrpl39I I39l flllilhll lxi l iili f39 i filial lll39gtl7lquot Hodentia l39n liw lujalrg illllli39l39393lf ll nul asl lwl t ilgll l Macmlidea will all 39Il39ll til ll l Primates tilltilll f Iurlillizg il39li lll jli milling i llllilill 5an a 53 ndentia trainee ral llwzlm Chiroptera hilt Dermoptera w uluvlm ll ll ill lelllulw IHEC EWDI E lil li diii iiil ilui l lquot1nlllrllll39il grin mu Gregjunta 1 CEI39I IWUI39E I lliw lrl Calif IZilii lljirfnilMil VolatilIEsalz l39l39lwi39i39lwl li l39l Zm39i lill llri iu Condylarthra 1 Artiodactyla whim lllta n iva a it Ll liriiiil a lull in lilll39liii yjti illilvllri l CEtECEEI l l lui llEaL lu ll l lll39lTi l39w ai l wfiIjaizisiin Tubulidentata viiil39rl ii l l Perisscdactyla llilifllIiL JIEJ ignl39vlla ilinintl wr39 Hy ramiclea l 1 la v Sirenia l l llullll l39lazvgzav ll M in l w ra w Desmcshylia 1 Embrythopxla 1 Probascidea Milkiil lil39llilu I l lii l ll39l rvilla l lllvslr39rul Erllililiu cl From httptolweborg UVa C5216 Spring 2006 Lecture 1 Analyzing Algorithms 6 Finding a Phylogeny Speculate on history based on current evidence Not guaranteed to be correct Find the most likely history Parsimony find the evolutionary tree that explains the observations with the fewest possible changes w smswm mus 7 mm I win mmmm Measuring Changes Natural Languages Grammatical Rules Lexicon Hard to quantify how similar two languages are Species Genomes only recently Easy to quantify genome differences are measurable w smswm mus 7 mm I win mmmm a How Species Evolve Point Mutations Substitution one base is replaced with another UV Ray With only point mutations easy to tell how close two CAT genomes are just count the different bases w smswm mus 7 mm I win warm How Species Evolve 2 Insertions one or more bases are inserted GCATG GCACATG Deletions one or more bases are removed GCATM GCATG Caused by copying errors enzymes slipping etc w smswm mus 7 mm I win mmmms 1n Measuring Genome Similarity o Insertions and Deletions this hard ACATCATCATCAT CATCATCATCATC are more similar than ACATCATCATCAT l l l l TCGTTCGCGAAAA w smswm was 7 mm 1 mum quot3910quotth Sequence Alignment Align sequences by inserting gaps ACATCATCATCAT llllllllllll CATCATCATCAT Find best alignment inserting gaps given value of matching bases point mutations 6 cost of a gap insertiondeletion g We use c10g2 g00dness12cig 118 w smswm was 7 mm 1 mum mmth 12 Brute Force Alignment To find the best alignment of sequences U and V with correct value c and gap penalty g if U or V is empty U V is the best alignment otherwise next slide w smswm mus 7 mm I win mmmm Course Structure Expectations Goals w smswm mus 7 mm I win mmmms 15 Meetings Lectures 2 per week Wil include material not in the book Most lectures will use slides and notes Section meetings 1 per week You must sign up for one of the sections Classroom work group exercises review quizzes Staffed time in Small Hall Take advantage of help from the ACs and your classma es w smswm was 7 mm 1 mum mmth IE Brute Force Alignment Otherwise Tn three possibilities Ul39 means U with the first element removed 1 First elements of U and Vare aligned score of best alignments of U1 and V1 c if UO 2 First element of U is aligned with a gap in V score of best alignments of U1 and V g 3 First element of Vis aligned with a gap in U score of best alignments of U and V1 9 Pick the choice with the highest score w smswm mus 7 mm I win mmmm Staff 0 Me David Evans Call me Dave or Coach Office Hours posted on course website Always available by email ifI don t reply in 24 hours send again and complain 0 Assistant Coaches Erika Chin David Faulkner Erin Golub Sam Guarnieri Katherine Jogerst and Pitchaya Yam SitthiAmorn Will lead Monday and Tuesday sections Available in Small Hall lab at posted times only w smswm mus 7 mm I win warm Problem Sets 8 total 1 212 weeks each Work on them when and where you want but take advantage of staffed lab time in Small Hall Usually will work with partners Mix of programming and analysis Main way most will learn Turn in on paper at beginning of class first is due Wednesday w smswm was 7 mm 1 mum quot3910quotth My Teaching Philosophy Drinking from a Firehose You will do fine It may hurt a little bit and a lot of water will go by you but you won t go away thirsty UVa CS216 Spring 2006 Lecture 1 Analyzing Algo i 1m 20 Expectations Math and Logic Background 0 You remember some things from C8202 or will learnre learn them when you need them Arithmetic logarithms sets graphs Symbolic logic implication Proof techniques induction contradiction o The textbook is quite mathematical you may need to read things more than once UVa CS216 Spring 2006 Lecture 1 Analyzing Algo i 1m 22 Course Goal 1 Learn to write deli htful programs correct readable elegant economical efficient scalable maintainable secure dependable UVa CS216 Spring 2006 Lecture 1 Analyzing Algo i 1m 24 Expectations Programming Background 0 You understand basic programming Can write a program longer than a screenful Can understand multifile programs Familiar with common control structures procedures recursive definitions 0 You don t freak out when you are expected to learn a new language on your own UVa CS216 Spring 2006 Lecture 1 Analyzing Algorithm Course Goals UVa CS216 Spring 2006 Lecture 1 Analyzing Algo 39thm Course Goal 2 Be able to predict how decisions about data representation will impact properties of an implementation running time memory use ease of implementation scalability UVa CS216 Spring 2006 Lecture 1 Analyzing Algo 39thm Course Goal 3 Understand how a program executes at levels of abstraction ranging from a high level programming language to machine memory We will talk about what this means in Monday s class w cszlsspnnq mus 7 mm 1 Anzlyxmq mmmms 25 Is this a good solution if U or V is empty U V is the best alignment othenNise Try three possibilities 1 First elements of U and Vare aligned score of best alignments of U1 and V1 c if UO VO 2 First element of U is aligned with a gap in V score of best alignments of U1 and V g 3 First element of Vis aligned with a gap in U score of best alignments of U and V1 9 Pick the choice with the highest score w cszlsspnnq mus 7 mm 1 Anzlyxmq mmmms 27 Algorithm Properties Implementable can be readily expressed as a program Termination always nishes Correctness always gives the correct answer Ef cient uses resources wisely Note Chapter 2 of text has a similar list but separates Implementable Into Effectiveness and Program Complexity w cszlsspnnq mus 7 mm 1 Anzlyxmq mmmms za Is It Implementable def bestAlignment U V c 39 if enU 0 or enV else U0 V0 bestAlignment U1 V1 c g sooreNoGap goodnessSoore 9 if U0 V0 scoreNoGap c remm UV try inserting a gap in U no match for V0 U1 V1 bestAlignment U V1 c g 500 GapU goodnssScore U1 V1 c g g try inserting a gap in V no match for U0 U2 V2 bestAlignment U1 V c g sooreGapV goodnessScore U2 V2 c g g w cszlsspnnq mus 7 mm 1 Anzlyxmq mmmms 29 Is It Implementable def bestAlignment U V c g iflenU 0 or len 0 room u v Siuo v0 bestAlignmentU1 v1 c g scoreNoGap goo nessScore uo v0 c g lfU0 VO scoreNoGap c a gap n u no match for vo U1 v1 bestAlignment u v1 c g scoreGapU goodnessScore U1 v1 c g r g a m inserting a a in v no match for uo U2 v2 bestAlignmentU1 v cg sc reGapV goodnessScore U2 v2 c g 9 if sooreNoGap gt sooreGapU and scoreNoGap gt scoreGapV retum U0 U0 V0 V0 elif scoreGapU gt sooreGapV retum GAP U1 VO v1 else return U0 U2 GAP V2 el Algorithm Properties Implementable can be readily expressed as a program Termination always finishes Correctness always gives the correct answer Ef cient uses resources wisely w cszlsspnnq was 7 mm 1 mum mmth an w cszlsspnnq was 7 mm 1 mum mmth a Lecture 8 Crash Course Computational Complexity car u r van7 7Axw r 4 39d r 11 7 2L L httpwwwcsvirginiaeducle6 Problems and Solutions 0 A problem defines a desired output for a given input 0 A solution to a problem is a procedure for finding the correct output for all possible inputs 0 The time complexity of a problem is the running time of the best possible solution to the problem UVa C5216 Spring 2006 Lecture 8 Computational Complexity 3 Brute Force Subset Sum Solution clef subsetsum items maxweight best for s in allPossibIeSubsets items if sum 5 lt maxweight and sum 5 gt sum best best 5 return best Running time 6 n2n What does this tell us about the time complexity of the subset sum probem UVa C5216 Spring 2006 Lecture 8 Computational Complexity 5 Procedures and Problems 0 So far we have been talking about procedures how much work is our brute force subset sum algorithm 0 We can also talk about problems how much work is the subset sum problem What is a problem What does it mean to describe the work of a problem UVa C5216 Spring 2006 Lecture 8 Computational Complexity Subset Sum Problem 0 Input set of n positive integers w0 Wn1 maximum weight W 0 Output a subset S of the input set such that the sum of the elements of SS W and there is no subset of the input set whose sum is greater than the sum of S and s W What is the time complexity of the subset sum probem UVa C5216 Spring 2006 Lecture 8 Computational Complexity Problems and Procedures 0 If we know a procedure that is that is 9001 that solves a problem then we know the problem is O 0 o The subset sum problem is in 012quot since we know a procedure that solves it in n2quot 0 Is the subset sum problem in nzn No we would need to prove there is no better procedure UVa C5216 Spring 2006 Lecture 8 Computational Complexity Lower Bound Can we find an Q bound for the subset sum problem It is in QM since we know we need to at least look at every input element Getting a higher lower bound is tough How much work is the Subset Sum Problem Upper bound 0 2quot Try all possible subsets Lower bound 9 n Must at least look at every element Tight bound 9 2 No one knows w csm Spnng 2m 7 man I Enmvuhonnal Ennvlaxl y w csm Spnng 2m 7 man I Enmvuhonnal Ennvlaxlh a intractable tractable sequen is a 4 5 a 7 a a 1011121314151617131920 1 do nothing tnata man ofunll39ml39ted funds superb physical en urance an maxlmum sclentl39 c kno wledge could not o 7 Batman may be able to solve intractable pro lems computer scientisls can on y solve tracla ble ones for large n Subset Sum Complexity Class P Tractable Class P problems that can be solved in polynomial time 0 nk for some constant k Easy problems like sorting sequence alignment simulating the universe are all in P w csm Spnng 2m 7 man I Enmvuhonnal Ennvlaxl y w csm spam 2m 7 man I Enmpuuonnal Ennvlaxlh 1n Complexity Class N P Class NP problems that can be solved in nondeterministic polynomial time If we could try all possible solutions at once we could identify the solution in polynomial time Alternately If we had a magic guess correctly procedure that makes every decision correctly we could devise a procedure that solves the problem in polynomial time w csm Spnng 2m 7 man I Enmpu aonnal Ennvlaxl y Complexity Classes Class P problems that can be solved in polynomial time 0011 for some constant k myopic problems like sequence alignment interval scheduling are all in P Class NP problems that can be solved in polynomial time by a nondeterministic machine includes all problems in P and some problems possibly outside P like subset sum w csm spam 2m 7 man I Enmpu aonnal Ennvlaxlh 12 Complexity Classes Possible View S equence Alignment 0n2 H W many problems are m the 00 class7 in H Hte How many problems are in P but not Either 0 or in nitel Interval Scheduling Subset Sum 0n log n 02quot and 2a w csm smg 2m umquot I common cumin Problem Classes if P c NP S equence Alignment 0n2 How many problems are in NP Lit not W P7 Infinite Interval Scheduling Subset Sum 0n log n 02quot and 2a w csm smg 2m umquot I common cumin Distinguishing P and NP Suppose we identify the hardest problem in NP let s call it Super Arduous Task SAT Then deciding is P NP should be easy Find a Ptime solution to SAT 3 P NP Prove there is no Ptime solution to SAT 3 P C w csm smg 2m umquot I common cumin P NP Is P different from NP is there a problem in NP that is not also in P If there is one there are infinitely many Is the hardest problem in NP also in P If it is then every problem in NP is also in P No one knows the answer The most famous unsolved problem in computer science and math Listed first on Millennium Prize Problems w csm smg 2m umquot I common cumin Problem Classes if P NP Sequence Alignment 0n2 How many problems are in NP but not In P7 Interval Scheduling Subset Sum 0n log n k w csm smg 2m umquot I common cumin The Satisfiability Problem SAT oInput a sentence in propositional grammar 0 Output Either a mapping from names to values that satisfies the input sentence or no way meaning there is no possible assignment that satisfies the input sentence w csm smg 2m umquot I common cumin CI Clausaelf Clause2 or Exa m p I e Clause1 A Clause2 and Name SATaVbCVlbC gt a true 1 false c true gt a true 1 true c false SAT a Ia gt no way w csm spam 2m tenure I Enmpuuonnal Ennvlexlb 19 The 3SAT Problem Input a sentence in propositional grammar where each clause is a disjunction of 3 names which may be negated Output Either a mapping from names to values that satisfies the input sentence or no way meaning there is no possible assignment that satisfies the input sentence w csm spam 2m tenure I Enmpuuonnal Ennvlexlb 2n 3SAT SAT Is 3SAT easier or harder than SAT It is definitely not harder than SAT since all 3SAT problems are also SAT problems Some SAT problems are not 3SAT problems w csm spam 2m tenure I Enmpuuonnal Ennvlexlb 21 Sentence Clause C u Clause1 vClause2 or Clause Clause1 A Clause2 and Exa mple 0 Clause Clause Clause 39 Name 3SAT avbv Ic lalbd aVbld bICd gt a true 1 false c false d false w csm spam 2m tenure I Enmpuuonnal Ennvlexlb 22 NP Completeness Cook and Levin proved that 3SAT was NP Complete 1971 as hard as the hardest problem in NP If any 3SAT problem can be transformed into an instance of problem Q in polynomial time than that problem must be no harder than 3SAT Problem Q is NPhard Need to show in NP also to prove Q is NPcomplete w csm spam 2m tenure I DumpMammal Ennvlexlb 2a Subset Sum is NP Complete o Subset Sum is in NP Easy to check a solution is correct 0 3SAT can be transformed into Subset Sum Transformation is complicated but still polynomial time A fast Subset Sum solution could be used to solve 3SAT problems w csm spam 2m tenure I Enmputaonnal Cowlexlb 24 Problem Classes if P 2 NP Sequence Alignment 0n2 How many problems are in the n class infinite How many problems are in P but not in the n class infinite How many problems are in NP but not NPComplete Note the NP Complete class is a 39 392 ring others In P 39in nite are circles Interval Schedulin g Subset Sum n10g n 3SAT UVa C5216 Spring 2006 Lecture 8 Computational Complexity 25 NPComplete Problems 0 Easy way to solve by trying all possible guesses o If given the yes answer quick in P way to check if it is right Assignments of values to names evaluate logical proposition in linear time Subset check if it has correct sum 0 If given the no answer no quick way to check if it is right No solution can t tell there isn t one UVa C5216 Spring 2006 Lecture 8 Computational Complexity 26 Traveling Salesperson Problem Input a graph of cities and roads with distance connecting them and a minimum total distant Output either a path that visits each with a cost less than the minimum or noT o If given a path easy to check if it visits every city with less than minimum distance traveled UVa C5216 Spring 2006 Lecture 8 Computational Complexity 27 Graph Map Coloring Problem Input a graph of nodes with edges connecting them and a minimum number of colors Output either a coloring of the nodes such that no connected nodes have the same color or no If given a coloring easy to check if it no connected nodes have the same color and the number of colors used UVa C5216 Spring 2006 Lecture 8 Computational Complexity 28 Minesweeper Consistency Problem Input a position ofn squares in the game Minesweeper Output either a 3 assignment of bombs to squares or no 0 If given a bomb assignment easy to check if it is consistent UVa C5216 Spring 2006 Lecture 8 Computational Complexity 29 Pegboard Problem UVa C5216 Spring 2006 Lecture 8 Computational Complexity 30 C82 16 Road map I Data Representation Program Representation LeCture 39 quot i 2851 Real World Problems 24 I 1 quot 5H Fast 7B y 39 quot39 EDEIISI Hel Objects Python ghter D I I c M V c H at in fart HI IiI IctIonarIes i l 1 i i I i i c code 39 Li 4 i xix 0x42381a addresses language 39 WSW Note depending on your i h CLARENDONPRESsOXPORD answers to the topic interest S lalrrttgujaghlac me exam question we might also A m I 0 look at another VM CLR or sse b y another assembly language RISC V I4UI VVUI Iu I httpwwwcsvirginiaeduc5216 UVa C5216 Spring 2006 Lecture 23 Fast Dictionaries 2 Fast Dictionaries Fast Dictionaries Data Representation o If the keys can be anything No best one comparison can Hello Objects 0 Problem set 2 question 5 You may assume Python s dictionary type provides lookup and insert operations that have do is eiiminate Hr 1H0 lt Arrays running times in 01quot 12 the elements 0x42381a 4 0 Class 6 fastest possible search using x39 The keys must be bits so we 01001010 can do better binary comparator is 0log n lCan Python really have an 01 lookup Bits UVa C5216 Spring 2006 Lecture 23 Fast Dictionaries 3 Wa C5216 Spring 2006 Lecture 23 Fast Dictionaries 4 LOOKUP Table Sparse Lookup Table Key Value 000000 red 0 Keys names words of up to 40 7 000001 orange bit ASCII characters 000010 blue 0 How big a table do we need 000011 null 4O 7 280 000100 green 2280 191084 entries 000101 white We need lookup tables where many keys can map to the same entry Works greatunless the key space is sparse UVa C5216 Spring 2006 Lecture 23 Fast Dictionaries 5 Wa C5216 Spring 2006 Lecture 23 Fast Dictionaries 6 o Hash Function h Key gt 0 ml H ere h firstLetterKey Collisions What if we need both Colleen and Cathy keys w csm smg 2m 7 mm 2 FasQDlzonnanes a Separate Chaining 0 Each element in hash table is not a ltkey valuegt pair but a list of pairs w csm smg 2m 7 mm 2 FasQDlzonnanes g Hash Table Analysis Lookup Running Time Worst Case N N entries all in same bucket Hopeful Case 01 Most buckets with lt 6 entries w csm smg 2m 7 mm 2 FasQDlzonnanes 1n Requirements for Hopeful Case Function h is well distributed for key space for a randomly selected k e K probability Mk i 1m Size of table m scales linearly with N Expected bucket size is Nm Finding a good h can be tough more later uvacszl spnngznn rlummza 5 Saving Memory Can we avoid the overhead of all those linked lists w csm smg 2m 7 mm 2 mum on 12 Linear Open Addressing w csm smg 2m 7 mm 2 FasQDlzonnangs 13 Sequential Open Addressing def lookup T k i hash k while not looped all the way around if Ti null return null else if Tikey return Tivaue else i i 1 mod Tength w csm smg 2m 7 mm 2 FasQDlzonnangs 14 Problems with Sequential Primary Clustering Once there is a full chunk of the table anything hash in that chunk makes it grow Note that this happens even if h is well distributed Improved strategy Don t look for slots sequentially i i 5 mod Tength Doesn t help just makes clusters appear scattered w csm smg 2m 7 mm 2 FasQDlzonnangs 15 Double Hashing Use a second hash function to look for slots i i hash2 K mod Tength Desirable properties of hash2 Should eventually try all slots result of hash2K should be relatively prime to m asiest to make m prime Should be independent from hash w csm smg 2m 7 mm 2 FasQDlzonnangs 15 Good Hash Functions Deterministic Arbitrary fixed size output Easy to compute Well distributed for a randomly selected k e K probability Mk i 1m w csm smg 2m 7 mm 2 mm Reasonable Hash Functions Just take the rst logm bits Just take the lowest 10g m bits Sum all key characters hash 21 kt mod m z m indexesk P56 Mystery code SHA 1 w csm smg 2m 7 mm 2 FasQDlzonnangs IE What does Python do long Pyobject ashwyobject v PyTypeObject tp vrgtobtype if havwihash l NULL return mrgtmhashv if mvtpicompare NULL my RICHcOMPAREnp NULL return Py ashpointeru Use address as hash value Types can have their own hash functions If there39s a cmp but no hash de ned the object can39t be hashed pyErrjesuingpyExcTypeError quotunhashable typequot 1 Python2 4Objectsobjectc W cm san 2m mm 23 moms 9 D i cti o n a ry Major subtleties ahmd Most hash schemes depend on having a quotgoodquot hash function in the sense of simulating randomness Python doesn39t its most important hash functions for strings and ints are very regular in oommon cases gtgtgt maphash 0 1 2 3 0123 n n gtgtgt map ash quotnamea namebquot quotnamec namedquot 1658398457 1658398460 1658398459 1658398462 gtgtgt This isn39t neoessarily bad Python24Objectsdictobjectc uvacszm Svnnqznn rlezmmzi nonwhmes 21 PyHash Pointer long Py ashporntermord p lf SIZEOFiLONG gt SlZEOFjOID retu rn ong p lquot convert to a Python long and hash that momech longob else ong x ll tllongom l vLol39lgfl nanolrlPu lpll NULL l x rt goto nally What does this Xv Pyomecr ashdongoml nally 7 mean for Python s P LXDECRttllongobjl lean x garbage collector erldlf To the contrary in a table of size 2i taking the loworder i bits as the initial table index is extremely fast and there are no collisions at all for dicts indexed by a contiguous range of ints The same is approximately true when keys are quotconsecutivequot strings So this gives betterthan random behavior in common cases and that39s very desirable OTOH when collisions occur the tendency to ll contiguous slices of the hash table makes a good collision resolution strategy crucial uva csm Shana 2m 7 lezmre 23Fa DIonnar1e 22 Collision Avoidance Taking only the last i bits of the hash code is also vulnerable for example consider i ltlt 16 fori in range20000 as a set of keys Since ints are their own hash codes and this fits in a dict of size 215 the last 15 bits of every hash code are all 0 they all map to the same table index uva csm Shana 2m 7 lezmre 23Fa DIonnar1e 2a Impact Scott Crosby Dan Wallach Denial of Service via Algorithmic Complexity Attacks USENIX Security 2003 Python Example 10000 inputs in dictionary Expected case 02 seconds Collision constructed case 20 seconds httpwwwcsriceeduscrosbyhash uva csm Shana 2m 7 lezmre 23Fa DIonnar1e 24 Lecture 3 Levels of Abstraction httpwwwcsvirginiaeduc5216 Recap BigO the set 003 is the set of functions that grow no faster than f There exist positive integers C no gt 0 such that fn S cgn for all n 2 n0 Omega 2 the set 203 is the set of functions that grow no slower thanf There exist positive integers C no gt 0 st fn 2 cgn for all n ZnO UVa C5216 Spring 2006 Lecture 3 Levels of Abstraction 3 Question from last class Given fe 0h and g e 0 h which of these are true a For all positive integers mfm ltg m a E v fE 0h Vge 0h v me Zfmltgm a is false gt not a E Ele 0h El ge 0hE me Zfm2gm this is exactly our counterexample Note this is very different from a claim like VfE 0h VgeE 0hE me Zfm2gm UVa C5216 Spring 2006 Lecture 3 Levels of Abstraction 5 Menu Orders of Growth 0 2 9 0 Levels of Abstraction List Datatype UVa C5216 Spring 2006 Lecture 3 Levels of Abstraction 2 Question from last class Given fe 0 h and g e 0 h which of these are true a For all positive integers mfm ltg m Proved false by counterexample Statement a is false so opposite of a must be true What is the opposite of statement a aEer Oh v g 0h v me Zfmltgm UVa C5216 Spring 2006 Lecture 3 Levels of Abstraction 4 What else might be useful 0n3 12712 n n25 n31 n2 UVa C5216 Spring 2006 Lecture 3 Levels of Abstraction 6 Theta Order ofquot Intuition the set f is the set of functions that grow as fast asf Definition fn e 9 g n if and only if both 1fn E 08 71 and 2fn E 9 801 Note we do not have to pick the same c and no values for 1 an When we say f is order g that means fn 6 G g 390 Tight Bound Theta 9 0013 n 12n2 n quot quot317 quot2 WW w smswm mus 7 mm a mu oIAbxlrzdlon 7 w smswm mus 7 mm a mu oIAbxlrzdlon a Little oh 0 Definition fe a g for all positive constants 6 there is a value n0 such that n S cgn for all n 2 no 0 Compare fe 0g there are positive constants c and n0 such that n S cgn for all n2 no Little Oh 0 0013 n 12n2 n n quot25 n quot317 quot2 w smswm mus 7 mm a mu uIAbxlrzdlon g w smswm mus 7 mm a mu uIAbxlrzdlon 1n Summary Big O there exist 6 no gt 0 such that n S cgn for all n2 no Omega 2 there exist 6 no gt 0 st n Z cgn for all n2 no Theta 9 both 0 and Q are true Litte o there exists no gt 0 such that for all c gt 0 n S cgn for all n2 no Trick Question If wealthn is your net worth n days after today would you prefer wealthn e 0n wealthn e 0n2 wealthm E 00 Which cgftthese are wealthn e Q n sal1n00001n Which is better weal 1n 100000000 Wealthn 00001n DJ 09g w smswm was 7 mm a mu oIAbxlrzdlon n w smswm was 7 mm a mu oIAbxlrzdlon 12 Levels of Abstraction Course Goal 3 Understand how a program executes at levels of abstraction ranging from a highlevel programming language to machine memory From Lecture 1 UVa C5216 Spring 2006 Lecture 3 Levels of Abstraction 13 UVa C5216 Spring 2006 Lecture 3 Levels of Abstraction 14 Levels of Abstraction Program Real World Problem High Level Program 39U C O M Virtual E PIJOM lealsAud VL achine Instructions H Physical Processor http www rci rutgersed ucfs472htmlIntrofl39inkertoyComputerTi nkerToy html TicTacToe Play TicTacToe x0 xy 390 O Ni III 39j 1 1 i oxStrategy l I quotXOX k 0 x xTicTac Toe UVa C5216 Spring 2006 Lecture 3 Levels of Abstraction 15 Sequence Alignment Program Genome Similarity High Level Program Alignpy H PIJOM lealsAud Virtual World Interpreter Python VL Low Level Program Electrons etc lt UVa C5216 Spring 2006 Lecture 3 Levels of Abstraction 17 7 Low level Tinker Toy Computer descr39ptlon UVa C5216 Spring 2006 Lecture 3 Levels of Abstraction 16 Levels of Abstraction Data Real World Things Data Abstraction 332 0 E 3 5 Low Level a n Data Structure Electrons etc UVa C5216 Spring 2006 Lecture 3 Levels of Abstraction 18 Levels of Abstraction PSl g g EE 1 0 Python List 2 8 5 E Electrons etc in csmswm mus 7 mm a mu mam List Operations Ch 3 Access L i returns the ith element of L Length L returns the number of elements in L Concat L M returns the result of concatenating L with M Elements lt10 1 s llLl71mOm139 mlMlylgt MakeEmptyListo returns lt gt IsEmptyListL returns true iff L 0 I15 this a sufficient list of List operations List Abstract Datatype Ordered collection datatype ltxo x1 xn71gt Operations for manipulating and observing elements of list w csmswm mus 7 mm a mu mam Constructing Lists The book s list operations have no way of constructing any list other than the empty list We need at least iAppem L c returns the result of appending c to L lt10 ll m I L71egt 21 w csmswm mus 7 mm a mu mam w csmswm mus 7 mm a mu mam Revised List Operations 32 Access L i returns Li Em Length L returns ILI ungxn39 Concat L M returns the result of inn L with M MakeEmptyListo returns ltgt IsEmEQListng returns true iff L O Append L e returns the result of appending e to L lt10 ll llurlegt I Are all of these operations necessary I Lp ua1 uisn auuap tn A523 w csmswm was 7 mm a mu mam 23 Necessary List Operations Access L i returns Li Length L returns ILI MakeEmptyListo returns ltgt Append L e returns the result of appending e to L lt10 ll llurlegt Note that we have de ned an immutable list There are no operations for changing the value of a list only making new lists w csmswm was 7 mm a mu mam Continuous Representation w smswm mus 7 mm a mu wand 25 Linked Representation Info I IInfo I IInfo I I Next Next Next we NOde Node We need a special value for Next when there is no Next node Book A C 0 Python None Scheme Java null w smswm mus 7 mm a mu wand 25 Necessary List Operations Access L i returns Li Length L returns ILI MakeEmptyListo returns ltgt Append L e returns the result of appending e to L lt10 ll llurlegt Can we implement all of these with both representation choices w smswm mus 7 mm a mu wand 27 Length Continuous Linked L def LengthL if one39 def LengthL return LLength return 0 return 1 LengthLNext w smswm mus 7 mm a mu wand 23 Which Representation is Better Time of Length n is number of elements Continuous 01 Linked 0n Are these bounds tight 6 What about other operations Other factors to consider Will explore this more next week uszSZISSvnnqmmrlulum m I wand 29 Python Lists Provide necessary operations iAccess L i Li iLength L lenL iMakeEmptyListO L iAppendL e Lappend e w smswm was 7 mm a mu mama an httpwwwcsvirginiaeducsZ 16 Question 10 We will discuss some Exam 2 In questions today We might do a E review Monday but only if enough E good questions are sent by Sunday E afternoon NET s VM 5 24 Instruct on set 218 Review 54 64 UVa C5216 Spring 2006 Lecture 25 Randomized Algorithms Question 10 Close vote hereluckiy there are many interesting randomized graph and network algorithms Imprc Partner Assignment Algor thms 1 4 Graph and Network Algor thms 12 37 Randomized Algorithms 9 38 NET s VM 5 24 Instruct on set 2 18 Review 54 64 Exam 2 Question 2 o In Class 16 we saw that the floating point imprecision in representing 01 led to an error of 00034 seconds per hour in the Patriot missile time calculations What clock tick unit would maximize the error accumulated per hour What is the error This was the easiest question but no one got it right UVa C5216 Spring 2006 Lecture 25 Randomized Algorithms UVa C5216 Spring 2006 Lecture 25 Randomized Algorithms Question 2 What is the smallest value the 24bit mantissa register can represent OOOOOOOOOOOOOOOOOOOOOOl 2391 23924 What if the clock tick is lt 23925 seconds Option 1 001 224 error gt 23925 per tick Option 2 000 0 error tick length per tick So error per hour is 1 hour Is this possible cModern Penium 4GHz Cock tick 14B s 1232 27 times faster than we need UVa C5216 Spring 2006 Lecture 25 Randomized Algorithms UVa C5216 Spring 2006 Lecture 25 Randomized Algorithms Question 4 Explain two reasons why it is easier to write a garbage collector for Python than it is to write a garbage collector for C Garbage Collection Stack Bottom of String args root Species 0 ss SpeciesSet Top or active all objects on shack while activeisEmpty 0 m e H foreach Object a in active M a rk a nd mark a as reachable nonrgarbage Swee p foreach ObJect 0 that a poms m If 0 Is not marked newac ve newactive u o Class 12 activ w c5215 spam 2m 7 lean1 25 Randnmlxed Ngunlhms 7 w c5215 spam 2m 7 lean1 25 Randnmlxed Ngunlhms a Question 9 Consider modifying the x86 calling convention to put the return value on the top of the stack when a routine returns instead of using EAX to hold the return value What are the advantages and disadvantages of this change w c5215 spam 2m 7 lean1 25 Rmdnmlxed Ngunlhms g Where could it go E 9 return address a a parameter 1 5 ESP 339 parameter 2 parameter 3 C calling convention state before ret w c5215 spam 2m 7 lean1 25 Rmdnmlxed Ngunlhms 1n Where could it go U result if R retum address 0 a parameter 1 g ESP 339 parameter 2 parameter 3 I Modi ed callIng YIkeS ret convention expects esp to be return address state before ret w c5215 spam 2m 7 lean1 25 Randnmlxed Ngunlhms 11 Puts it before RA return address m result 5139 9 result 0 g parameter 1 g ESP Implications Caller must reserve enough space on stack to hold results w c5215 spam 2m 7 lean1 25 Randnmlxed Ngunlhms 12 Is this a good idea 0 Advantages Frees up EAX for other things Allows longer return values 0 Multiple results Python 0 Return arrays structures 0 Disadvantages Stack access can be a lot slower than registers If caller uses result it probably needs to copy it into a register anyway UVa C5216 Spring 2006 Lecture 25 Randomized Algorithms 13 Randomized Algorithms Sample Programs x fa X f g h a y gb z fX y Which code fragment could be faster with the new convention UVa C5216 Spring 2006 Lecture 25 Randomized Algorithms 14 Why use randomness 0 Avoid worstcase behavior randomness can probabilistically guarantee average case behavior 0 Efficient approximate solutions to intractable problems UVa C5216 Spring 2006 Lecture 25 Randomized Algorithms 15 UVa C5216 Spring 2006 Lecture 25 Randomized Algorithms 16 Randomized Algorithm Deterministic Output Computer 1 Random bits Input 39 wwwlavarndorg I doesn t use lava lamps anymore UVa C5216 Spring 2006 Lecture 25 Randomized Algorithms 17 Types of Algorithms 0 Monte Carlo Running time bounded by input size but answer may be wrong Decision problems If there is no solution always returns no If there is a solution finds it with some probability gt 12 Value problems run for a bounded number of steps produce an answer that is correct approximation with a bounded probability function of number of steps UVa C5216 Spring 2006 Lecture 25 Randomized Algorithms 18 Types of Random Algorithms 0 Las Vegas Guaranteed to produce correct answer but running time is probabilistic 0 Atlantic City Running time bounded by input Can return either yes or no regardless of correct answer Correct with probability gt 23 How could this be useful Determining 71 01 Square 1 Circle 714 The probability a random point in square is in circle 7t4 00 TC 4 points in Circlepoints UVa CS216 Spring 2006 Lecture 25 Randomized Algorithms 19 UVa CS216 Spring 2006 Lecture 25 Randomized Algorithms 20 Find 71 def findPi points incircle 0 for i in range points X randomrandom y randomrandom if square X 05 square y 05 lt 025 025 rA2 incircle incircle 1 return 40 incircle points Monte Carlo or Las Vegas UVa CS216 Spring 2006 Lecture 25 Randomized Algorithms 22 UVa CS216 Spring 2006 Lecture 25 Randomized Algorithms 21 Results ml 40 40 00 m2 20 40 40 m4 30 40 30 In 64 30625 3125 30625 If we wait long enough will it produce an arbitrarily accurate value n 1b584 512b2200511 114058085958 511919b8 n 131072 313494873047 314785766602 313766479492 n 1048576 314015579224 314387893677 314112472534 5 I Minimum Cut Problem 0 Input an undirected connected multigraph G V15 0 Output A cut V1V2where Vl u V2 V and V1 m V2 6 such that number of edges between V1 and V2 is the fewest possible Why might this be useful Equivalent fewest edges that can be removed to disconnect G UVa CS216 Spring 2006 Lecture 25 Randomized Algorithms 23 UVa CS216 Spring 2006 Lecture 25 Randomized Algorithms 24 Minimum Cut Size of the min cut must be no larger than the smallest node degree in graph UVa C5216 Spring 2006 Lecture 25 Randomized Algorithms 25 Internet inimum Cut itlxl June 1999 Internet graph Bill Cheswick httpresearchlumetacomchesmapgalleryindexhtml UVa C5216 Spring 2006 Lecture 25 Randomized Algorithms 26 Randomized Algorithm 0 While V gt 2 Pick a random edge xy from E Contract the edge 0 Keep multi edges remove self loops 0 Combine nodes 0 The two remaining nodes represent reasonable choices for the minimum cut sets UVa C5216 Spring 2006 Lecture 25 Randomized Algorithms 27 Analysis 0 Suppose C is a minimum cut set of edges that disconnects G c When we contract edge e Unlikely that e e C So C is likely to be preserved What is the probability a randomly choosen edge is in C UVa C5216 Spring 2006 Lecture 25 Randomized Algorithms 28 Analysis 0 Is the final result a cut of G o What is the probability we find a minimum cut UVa C5216 Spring 2006 Lecture 25 Randomized Algorithms 29 Random Edge in C C must be 3 degree of every node in G o How many edges in G E sum of all node degrees 2 2 nICI2 Probability a random edge is in C s 2n UVa C5216 Spring 2006 Lecture 25 Randomized Algorithms 3o Lecture 16 Numbers httpwwwcsvirginiaeduc5216 Directions for Getting 6 1 Choose any regular accumulator ie Accumulator 9 2 Direct the Initiating Pulse to terminal 5139 3 The initiating pulse is produced by the initiating unit39s Io terminal each time the Eniac is started This terminal is usually by default plugged into Program Line 11 described later Simply connect a program cable from Program Line 11 to terminal 5ion this Accumulator 4 Set the Repeat Switch for Program Control 5 to 6 5 Set the Operation Switch for Program Control 5 to ADD 6 Set the ClearCorrect switch to C 7 Turn on and clear the Eniac 8 Normally when the Eniac is first started a clearing process is begun If the Eniac had been previously started or if there are random neons illuminated in the accumulators the Initial Clearquot button of the Initiating device can be pressed 9 Press the Initiating Pulse Switchquot that is located on the Initiating device 10Stand back UVa CS215 Spring 2005 Lecture 15 Numbers 3 Binary Number Representations First presented by Gottfried Leibniz 1705 Explication de l Arithm tique 39 39 s and 39gquotd d 39 l3htlf L39bquot ee wwcsvl Inlaeuevansaca emlcroo mlor elnlzs h w advising relationship to me academic gral1 grandadvsor George Boole Boolean logic 1854 Claude Shannon s 1937 Master s thesis implemented Boolean algebra with switches and relays Used by AtanasoffBerry Computer Colossus and Z3 UVa CS215 Spring 2005 Lecture 15 Numbers 5 Started 1943 early electronic programmable computer 0 Operational in 1946 Computed ballistics tables 1 I 17468 ac m 39 IA k tubes V W Earlier Computers Z3 Konrad Zuse 1941 o 150 kW 0f power Colossus 1943 UVa CS215 Spring 2005 Lecture 15 Numbers ENIAC number representation Decimal system Ring of 36 vacuum tubes to store one digits 10 flipflops to store 09 Designed to emulate mechanical adding machine electronically 20 accumulators registers each stores 10digits 5000 cycles per second Perform additionsubtraction between 2 accumulators each cycle UVa CS215 Spring 2005 Lecture 15 Numbers Binary Representation bnlbnan3 39b2b1b0 0 0 0 0 1 1 139 1 0 1 Value 2b 2 11 0 i On1 What should n be UVa CS215 Spring 2005 Lecture 15 Numbers 6 What is n 0 Java byte char 8 bits short 16 bits int 32 bits ong 64 bits 0 C implementationdefined int can hold between 0 and UINTiMAX o UINX7MAX must be at least 65535 n gt 16 typical current machinesn 32 0 Python n is not fixed numbers work Wa c5215 Spring mus Lecture ls Numbers End la n ness Its a religious argument names taken from Big Endians and Little Endians in Gulliver s Travels who argued over which end of an egg to crack Different orderings problematic Consider what ltlt means in C 0 big endian divide by 2 0 little endian multiply by 2 Some architectures support both bi endian PowerPC DEC Alpha IA64 Most Internet standards big endian The Great Debate 0 Big Endian most significant first lowest address 1000 0000 0000 0000 215 32768 0 Little Endian most significant last highest address 1000 0000 0000 0000 2 1 Which is better Wa csus Spring 2nns Lecture ls Numbers Other Kinds of Numbers 0 Positive and Negative Integers Sign Bit Ones Complement Twos Complement Section this week 0 Real numbers Wa csus Spring 2nns Lecture ls Numbers 9 Wa csus Spring 2nns Lecture ls Numbers Real Numbers 13 TC 01 3333333333333 10391 V2 Wa csus Spring 2nns Lecture ls Numbers 11 Pentium II Wa csus Spring 2nns Lecture ls Numbers IEEE Floating Point Single Precision 32 bits 1 8 bits 23 bits 5 Exponent Fraction 31 30 23 22 0 Exponent 0 zeroes vaues 1254 exp 127 255 infinities NaN Value 1 2Sign 1 Fractianfxpmmquot 127 UVa szis Staring was r imm is Numbers 13 Fraction I b1b2b3b4b5b6b7b8b9b10b11b12b13b14b15b16b17b18b19b20b21b22b Fraction Z biZl39 i123 uVaESZIs SDnannns rum is Numbers IEEE Floating Point Single Precision 32 bits 1 8 bits 23 bits Exponent I Fraction I 31 30 23 22 0 Value 1 2Sign 1 Fractianyxpmem39 127 What is the largest float exponent 11111111 255 fraction 1 2 12i z 113 UVa szis Svnnq was r imm is Numbers 15 Example 110 01 Decimal What is this in binary 110 e 116 132 332 232 2320 e 1256 1512 a J 3512 1875320 0011001100110011 UVaESZIs SDnannns rum is Numbers 0001100110011001100110011 1010 100000000000000000000000000 1100 1010 10000 1010 1100 Even common decimals like 01 cannot be represented exactly Patriot Missile 0 Gulf War I 0 Failed to intercept incoming Iraqi scud missile Feb 25 1991 o 28 American soldiers killed GAO Report GAOllVlTEC792726 Patriot Missile Software Problem http www res orgSPPStarwarsgaDim92D26 Him ma szis Staring was r imm is Numbers 17 uVaESZIs SDnannns rum is Numbers Patriot Design 0 Intended to operate only for a few hours Defend Europe from Soviet aircraft and missile 0 Four 24bit registers 1970s design 0 Kept time with integer counter incremented every 110 second 0 Calculate speed of incoming missile to predict future positions velocity loc1 locDcount1 countu 01 0 But cannot represent 01 exactly Floating Imprecision 24 bits 01 124 125 128 129 1212 1213 1216 1217 1220 1221 209715 2097152 Error is 022097152 110485760 One hour 3600 seconds 3600 110485760 10 000345 20 hours 006875 w c5216 swung 72m in Nunhers 19 uvacszm swung 2m 7 mm m Nunhas 2n Two weeks before the incident Army officials received Israeli data indicating some loss in accuracy after the system had been running for 8 consecutive hours Consequently Army officials modified the software to improve the system39s accuracy However the modified software did not reach Dhahran until February 26 1991 the day after the Scud incident Better Floating Point Use More Bits IEEE Double Precision 64 bits 1 11 bits 52 bits Single Precision 1 2097152097152 Error 95quot10 E 20 hours to miss target Double Precision 0 1 56294995342131552949953421312 GAO Report Error 3608 quot1015 2172375450 years to miss w c5216 Sta ugznmi 722m 5 mi 2 uvacszm smug 2m 7 m 5 mm 22 Better Floating Point 0 IBM Floating Point Hexadecimal Use more bits in fraction fewer in exponent 724 and 756 instead of 823 and 1152 Decimal Formats IEEE 754d Naive 1 decimal digit into 4 binary digits Cowlishaw encoding o Exact representation of decimals eg 01 o 3 decimal digits 0999 into 10 binary digits 01023 24 wasted out of 1024 Smaller Floating Point 0 16 bit floating point representations Minifloat 1 sign 5bit exponent 15 10bit mantissa Range from 298gtlt10 8 to 65504 Your graphics card uses this if you have a good one VIDIA 4OB Floating Point Ops per second 3GHZ Pentium 128 w c5216 swam 72m in Nunhers 23 uvacszm swung 2m 7 mm m Nunhas 24 Lecture 20 HairDryer Attacks and Introducing Image from wwwcleanfunnycom GoldenBlue LLC Java Security r gt r J39thac malcodeclass malcodegavarH com pile r JVML axa 39 BYteicode Verifier InvaHd Okay Trusted Computing Base httpwwwcsvirginiaeducle6 UVa C5216 Spring 2006 Lecture 20 Introducing Asm Bytecode Verifier Checks JVML code satisfies safety properties Simulates program execution to know types are correct but doesn t need to examine any instruction more than once After code is verified it is trusted is not checked for type safety at run time except for casts array stores Key assumption when a value is written to a memory location the value in that memory location is the same value when it is read Violating the Assumption The object on top of the stack is a SimObject astore0 There is a SimObject in location 0 aload0 The value on top of the stack is a SimObject If a cosmic ray hits the right bit of memory between the store and load the assumption might be wrong UVa C5216 Spring 2006 Lecture 20 Introducing Asm 3 UVa C5216 Spring 2006 Lecture 20 Introducing Asm Improving the Odds Set up memory so that a single bit error is likely to be exploitable o Mistreat the hardware memory to increase the odds that bits will flip Following slides adapted with permission from Sudhakar Govindavajhala and Andrew W Appel Using Memory Errors to Attack a Virtual Machine July 2003 Making Bit Flips Useful Fi up memory with Filler objects and one Pointee obJect class Filler class Pointee Pointee a1 Pointee a1 Pointee a2 Pointee a2 Pointee a3 Filler f Pointee a4 int b Pointee a5 Pointee a5 Pointee a6 Pointee a6 Pointee a7 Pointee a7 UVa c5215 Spring 2005 Lecture 20 Introducing Asm 5 UVa C5216 Spring 2006 Lecture 20 Introducing Asm al Fllllng Up a U a3 a M emory L54 8 as g Pointee p new volume 0 56 l Vector llers new Vector o 57 m a1 while true a2 g Filler f new Filler 0 f E a p a2pfa3pfa7 p g fillersadd f b 2 as E camh OutOlMemoryException e l T 8 a7 al Flller Object t a2 mm mm m 54 f 1 al 52 Type Vlolatlon Lzas a4 8 After the bit flip the 5 a value of fa2 is a a7 Filler object but 6 a fa2 was declared t g 0 as a Pomtee object ab 2 g a Can an attacker exploit this a SKE Flller Object a quotV2 E5216 Spnng 2am r tenure 2n lmmduung Asm a 9 Safety if fa1 Object fa1 fa1b fr a fra4 fa1b Violating Type class Flller class Polntee U 9 m m Polntee a5 Polntee a6 Polntee a6 Polntee a7 Polntee a7 Filler f Filler enextEement O 39 p bit ipped r a Filler fr Filler r Cast is checked at runtime Decla red Ty pe int Filler Pointee 51 Walt for a blt a U 1 a3 a 54 g 0 Remember there are 5 5 lots of Filler objects 5 67 fill up all of memory 1 o If a bit flips good a2 g chance 70 o it will f g be in a field of a Filler b 3 object and it will now 5 5 9 point to a Filler object 5 instead of a Pointee bar 51 ObJeCt Flller Object t a2 w c5216 sma 2m 7 M 2m manual 5 a4 Pomtee p new Poll lme O 39 Vector llersnewvecmr0 Flndlng the Blt WT Whlle true l 39 Flller r new Flller o I p m p a2 3 fail p fa7 p llers add 0 W while true for Enumeration e llerseemenls ehasMoreE emenls Filler f Flller enextEement 0 if al p bit ipped eise if faZ p w csm Spnng 2m 7 lezmre 2n lnhudunng Asm w csm Spnng 2m 7 lezmre 2n mmde Asm class Flller class Polntee Violating Type Safety Pointee a3 Filler f Polntee a7 Polntee a7 Filler f Flller enextEement 0 if al p bit ipped O jectr a Filler fr Filler r Cast is checked at runtime fal 15 43 3 less of the Secun39tyManager fra4al nu I et it to a null Do whatever you want No security policy now new Flle Cd1esisdocquotdelete w csm Spnng 2m 7 lezmre 2n mmde Asm Getting a Bit Flip Wait for a Cosmic Ray You have to be really really patient or move machine out of Earth s atmosphere XRays Expensive not enough power to generate bit flip High energy protons and neutrons Work greatl but you need a particle accelerat Hmm uVa C5216 Spring 2006 Lecture 20 Introducing Asm 13 Using Heat 0 50watt spotlight bulb 0 Between 80 100 C memory starts to have a few failures 0 Attack applet is successful at least half the time o Hairdryer works too but it fries too many bits at once uVa C5216 Spring 2006 Lecture 20 Introducing Asm 14 Should Anyone be Worried Java virtual machine uVa C5216 Spring 2006 Lecture 20 Introducing Asm 15 Reca p o Verifier assumes the value you write is the same value when you read it o By flipping bits we can violate this assumption 0 By violating this assumption we can violate type safety get two references to the same storage that have inconsistent types 0 By violating type safety we can get around all other security measures 0 For details see paper linked from notes uVa C5216 Spring 2006 Lecture 20 Introducing Asm 16 C8216 Roadmap Data Representation Program Representation Real World Problems Hello ObJeCtS Python High 39eVel H i 0 Arrays code Langlfagel 0x42381a AddresseS C code Iaor l V39ugV 314 Numbers 9 g X Characters JVML Eigzuja39gl e39achine x86 Assembly 01001010 Bits Real World Physics uVa C5216 Spring 2006 Lecture 20 Introducing Asm 17 From JVML to X86 0 More complex instructions JVML 1 byte opcodes all instructions are 1 byte plus possible params on stack x86 1 2 and 3 byte opcodes Lowerlevel memory JVML stack and locations managed by VM x86 registers and memory managed mostly by programmer IWhy is x86 instruction set more complex uva C5216 Spring 2006 Lecture 20 Introducing Asm 18 X86 History c 19605 Project Apollo o 1971 Intel 4004 Processor First commercial microprocessor Target market calculators UVa C5216 Spring 2006 Lecture 20 Introducing Asm 19 16 4bit registers Intel 4004 Flag lilyFlops 3deep stack UVa C5216 Spring 2006 Lecture 20 Introducing Asm 2o X86 History 0 1971 4004 46 instructions 41 8bit wide 5 16bits Separate program and data store 0 1974 8080 8bit processor Used in MITS Altair 1978 8086 8088 16bit architecture Assembly backwards compatible with 8080 UVa C5216 Spring 2006 Lecture 20 Introducing Asm 21 X86 History 1982 80186 Backwards compatible with 8086 Added some new instructions 1982 80286 1986 386 First 32bit version but still backwards compatible with 16bit 8086 1989 486 Added a few instructions 1993 PentiumTM can t trademark numbers Now Athlon 64 X8664 64bit versions but still backwards compatible UVa C5216 Spring 2006 Lecture 20 Introducing Asm 22 X86 Registers 16 bits 8 bits 8 bits U E EAX U 3905 EBX o 8 ECX o lt D S EDX 9 E 5 ESI 6 w k EDI ESP stack pointer EBP base pointer 32 bits quot instruction pointer UVa C5216 Spring 2006 Lecture 20 Introducing Asm 23 X86 Instructions 0 Variable length 117 bytes long average is 3 bytes Opcodes 14 bytes long eg 660F3AOFC108H PALIGNR Parameters registers memory locations constants Need different opcodes to distinguish them UVa C5216 Spring 2006 Lecture 20 Introducing Asm 24 Lecture 7 Greedy gt Algorithms v I V i A httpwwwcsvirginiaeducsZ16 Menu La vita e incerta mangia il dolce per primo Life is uncertain Eat dessert first Ernestine Ulmer UVa C5216 Spring 2006 Lecture 7 Greed is Good Greed is Good 0 Adam Smith An Inquiry into the Nature and Causes of the Wealth of Nations 1776 It is not from the benevolence of the butcher the brewer or the baker that we expect our dinner but from their regard to their own interestsquot 0 Invisible hand individuals acting on personal greed produces nearly globally optimal results Greedy Algorithms 0 Make the locally best choice myopically at each step Need to figure out what dessert is 0 Hope it leads to a globally good solution Sometimes can prove it leads to an optimal solution Other times like phylogeny non optimal but usually okay if you get lucky UVa C5216 Spring 2006 Lecture 7 Greed is Good 3 UVa C5216 Spring 2006 Lecture 7 Greed is Good Interval Scheduling Problem 0 Input R a set of n resource requests lts0f0gt lts1f1gt lts1 f1gt 0 Output a subset S of R with no overlapping requests s gt s ltf for any ltsfgt ltsjfjgt e S such that ISI 2 lTl for any TgR with no overlapping requests UVa C5216 Spring 2006 Lecture 7 Greed is Good 5 Example R lt0 3gt lt1 2gt lt1 5gt lt2 5gt lt25 4gt lt4 45gt UVa C5216 Spring 2006 Lecture 7 Greed is Good Solution R lt0 3gt lt1 2gt lt1 5gt lt2 5gt lt25 4gt lt4 45gt w ESZIsSpmq mus mu 1 Greed ma Brute Force Algorithm Try all possible subsets Filter out ones with overlapping intervals Pick the largest subset Running time How many subsets 2quot Constant work for each subset Zn w ESZIsSpmq mus mu 1 Greed ma Greedy Approaches Need to pick best subset by making myopic decisions one element at a time Many possible criteria for making myopic decision Earliest starting time Latest ending time Shortest w ESZIsSpmq mus mu 1 Greed ma Greedy Approach Earliest Starting Not optimal ISI lt lbestl 3 w ESZIsSpmq mus mu 1 Greed ma Greedy Approach Earliest Finishing Not optimal lSl lt Ibestl 3 w ESZIsSpmq mus mu 1 Greed ma Greedy Approach Shortest Length w ESZIsSpmq mus mu 1 Greed ma Greedy Approach Shortest Length R lt0 25gt lt2 3gt lt25 5gt Not optimal ISI lt lbestl 2 VzESZISSvnnq mmrl11lum7 medlx ood 13 Greedy Approach Pick Earliest Finishing Time o H N be 4 U1 VzESZISSvnnq mmrl11lum7 medlx ood 14 Greedy Algorithm Running Time Analysis Straightforward implementation Search to find earliest finishing 0n Eiminate matching elements 0n Repeat up to n times 00 Smarter implementation Sort by finishing time On log n Go through list selecting if non overlapped 0n Running time 6 On log n VzESZISSvnnq mmrl11lum7 medlx ood 15 Correctness How to prove a greedy algorithm is nonoptimal Find a counterexample some input where the greedy algorithm does not find the best solution How to prove a greedy algorithm is optimal By induction always best up to some size By exchange argument swapping any element in solution cannot improve result VzESZISSvnnq mmrl11lum7 medlx ood 15 Proof The greedy algorithm produces R r0 rk71 Suppose there is a better subset Q 10 M 511171 9k Sort both by finishing time so fylltfyj for all 0g iltjltk fqlltqu for all 0g iltjltk1 VzESZISSvnnq mmrl11lum7 medlx ood 17 Proof R r0 rk71 Q 10 aqk715qk fylltfyj for all 0 iltjltk fqlltqu for all 0 iltjltk1 Strategy 1 Prove by induction f if for all iltk 2 Then since fw1 qukrlif q is valid it would have also been added to R VzESZISSvnnq mmrl11lum7 medlx ood IE Induction Proof f squ R r0 mrk71 0 Basis f0 quo Greedy algorithm choose rDas the element wit the earliest finishing time 501105 for all 0 Induction fur1 Sf 1 2f qu Since f if we know sqlzfm So greedy algorithm co ld choose 1 Iffqllt fv greedy algorithm would have chosen 39 t ad fa ins e Q 10 m 11M 11k Knapsack Problems You have a collection of items each has a value and weight How to optimally fill a knapsack with as many items as you can carry Scheduling weight time one deadline for all tasks Budget allocation weight cost m oms swing ms mime 1 Greed om m EZISSPruq ms lulure l Grad IsEood General Knapsack Problem Input a set of n items ltuameovalueo weighty ltnamen71 valuenrl weightnrlgt and maxweight Output a subset of the input items such that the sum of the weights of all items in the output set is s maxweighz and there is no subset with weight sum Smaxweight with a greater value sum Brute Force Knapsack def knapsack items maxweight bestvalue 0 for sin allPossibleSubsets items u 0 wei ht 0 for item in 5 value itemvalue weight itemweight if weight lt maxweight if value gt bestvalue Defining and analyzing this might be a good Xam 1 question best s bestvalue value return best m oms swing ms mime 1 Greed om m EZISSPruq mo lulull l Grad IsEood Brute Force Knapsack Analysis How many subsets are there How much work for each subset for item in 5 value item value Weigh item Weight Average size of each subset is n2 there are as many subsets with size 6 and of size nee Running time 6 012 Dynamic Programming Section this week dynamic programming solution to the knapsack problem Running time in 0mwcweight n m oms swing ms mime 1 Greed om m EZISSPruq ms lulull l Grad IsEood Greedy Knapsack Algorithm Repeat until no more items t Add the most valuable item that fits Greedy always picks the most valuable item that fits first w smsmm mus mime 1 Greed em Is Greedy Algorithm Correct No Proof by counterexample Consider input items lt gold 100 1 gt lt platinum 110 3gt lt silver 80 2 gt maxweight 3 Greedy algorithm picks lt platinum gt value 110 but lt gold gt silver gt has weight lt 3 and value 180 w smsmm mus mime 1 Greed em Greedy Algorithm Correct 0 It keeps adding items until maxweight would be exceeded so the result contains k items where kwlt maxweight and kIw gt maxweight 0 Hence cannot add any item weight w without removing another item 0 But any item with value gt value of the lowest value item in result would have already been added by greedy algorithm w smsmm mus mime 1 Greed em Greedy Knapsack Algorithm def knapsackigreedy items maxweight l 2 try to add the best item weightleft maxweight 7 weight Ru nn39 9 Tlme bestitem None 6 n2 for item in items if itemweight lt weightleft item ne or itemvalue gt bestimmyalue bestitem item if bestitem None break else resultappend bestitem weight bestitemweight ietui n resu w smsmm mus mime 1 Greed em Same Weights Knapsack Problem Input a set of n items ltname0va1ue0gt ltnamen71 valuen71gt each having weight w and maxweight Output a subset of the input items such that the sum of the weights of all items in the output set is S maxweightand there is no subset with weight sum Smaxweight with a greater value sum w smsmm mus mime 1 Greed em Subset Sum Problem Knapsack problem where value weight Input set of n positive integers w0 ww maximum weig t W Output a subset S of the input set such that the sum of the elements of S W and there is no subset of the input set whose sum is greater than the sum of S and S W w smsmm mus mime 1 Greed em C3216 Roadmap Data Representation Program Representation Real World Problems Lecture 17 OXCAFEBABE Highlevel n Objects Python HIljlielllg Arrays code language Vlrtual W OX42381a Addresses C code tacgwgvgl Machines 3 314 Numbers g g 397 39 Chara Cte rs Vlrtual Machlne I X language x86 Assembly 01001010 Bits Real World Physics http IWWW CSVl rg l nia Gd UCSZ 16 UVa C5216 Spring 2006 Lecture 17 Bytecodes 2 amp JavaTM Programming Language t Fig A snmple obJectoriented Java Virtual Machine distributed interretedl robust neutral JVM L is a detour ncd everything else we have multl hreaded an amic seen is part of running the PSI Iangu e Sun95 Python program P ropertIes of language WEdneSday39S CIaSS implementations not languages JavaTM Programming Language JVML compared To C not To C sort of I A I t t CIA I a oodeclass snmp e o Jec orIen e Java 2 distributed interpreted robust 333 ComP39Pi m secure architecture neutral Code portable hihperformance multithreaded and dynamic language Sun95 Java int is 32 bits C int is gt 16 bits UVa C5216 Spring 2006 Lecture 17 Bytecodes 5 UVa C5216 Spring 2006 Lecture 17 Bytecodes 6 Java Virtual Machine 0 Small and simple to implement o All VMs will run all programs the same way 0 Secure Java Ring 1998 Implementing the JavaVM load class into memory set the instruction pointer to point to the beginning of main while not finished fetch the next instruction execute that instruction Some other issues we will talk about Wednesday Verification need to check byte codes satisfy security policy UVa C5216 Spring 2006 Lecture 17 Bytecodes 7 UVa C5216 Spring 2006 Lecture 17 Bytecodes Java Byte Codes Stackbased virtual machine 0 Small instruction set 202 instructions all are 1 byte opcode operands Intel x86 28O instructions 1 to 17 bytes long 0 Memory is typed Every Java class file begins with magic number 3405691582 OXCAFEBABE in hex StackBased Computation push put something on the top of the stack 0 pop get and remove the top of the stack Stack push 2 2 5 push 3 3 add Does 2 pops pushes sum UVa C5216 Spring 2006 Lecture 17 Bytecodes 9 UVa C5216 Spring 2006 Lecture 17 Bytecodes 10 Some JVML Instructions Description Opcode Mnemonic O nop Does nothing 1 aconstnull Push null on the stack 3 iconstO Push int 0 on the stack 4 iconst1 Push int 1 on the stack Why do we need both aconstnull and iconstO Load Constant Opcode Mnemonic Description 18 ldc ltvauegt Push a one word 4 bytes constant onto the stack Constant may be an int float or String ldc Hello ldc 216 The String is really a reference to an entry in the string constant table UVa C5216 Spring 2006 Lecture 17 Bytecodes 11 UVa C5216 Spring 2006 Lecture 17 Bytecodes 12 Arithmetic 0pcode Mnemonic Description 96 iadd Pops two integers from the stack and pushes their sum iconst72 iconst73 iadd w csm smg 2m 7 mm 17 ammdu 13 Java Byte Code Instructions 0 nop 1 20 putting constants on the stack 96 119 arithmetic on ints longs oats doubles 1 byte opcode 146 left What other kinds of instructions do we nee w csm smg 2m 7 mm 17 ammdu 15 Arithmetic two inmgers pushe two Other Instruction Classes Control Flow 20 instructions if goto return Loading and Storing Variables 65 instructions Method Calls 4 instructions Creating objects 1 instruction Using object fields 4 instructions Arrays 3 instructions w csm smg 2m 7 mm 17 ammdu 15 Control Flow ifeq ltlabelgt Pop an int off the stack If it is zero jump to the label Otherwise continue normally ificmple ltlabelgt Pop two ints off the stack If the second one is lt the first one jump to the label Otherwise continue normally Referencing Memory iload ltvarnumgt Pushes the int in local variable ltvarnumgt 1 bytes on the stack istore ltvarnumgt Pops the int on the top of the stack and stores it in local variable ltvarnumgt w csm smg 2m 7 mm 17 ammdu 17 w csm smg 2m 7 mm 17 ammdu IE v vvv39v I m 7 39 gt ttl b39 4 J S we 60 1 Le ctu re 1 9 vi wgllllfailliiiiil I h H IN oEbEL P i 7 Java Security j H v quot ETHEF39 m j j 39 ING WIPES QLLow L PS6 Submission l WHOLE Emmeis w m Only to be eligible l 39 for the Byte Code Wizard awards If the web submission is down you can submit once by email 9 it i 3951 l 1 w 39 l f l l l a I l httpwwwcsvirginiaeducle6 Running Mistyped Code method public static mainLjavalangStringV iconst2 istore0 aload0 iconst2 iconst3 iadd gt java Simple Exception in thread quotmainquot javalangVerinyrror class Simple method main signature LjavalangStringV Register 0 contains wrong type return gt java noverify Simple end method result 5 UVa C5216 Spring 2006 Lecture 19 Java Security 2 Running Mistyped Code method public static mainLjavalangStringV gt java noverify Simple Idc 216 Unexpected Signal EXCEPTIONACCESSVIOLATION 0xc0000005 occurred at PC0x809DCEB 39Store O FunctionJVMFindSignaI0x1105F aload0 LibraryCj2dk142jrebinclientjvmd EconSt Z Current Java thread ICOnSt3 at SimplemainSimpIejava7 iadd 39 HotSpot Virtual Machine Error EXCEPTIONACCESSVIOLATION end methOd Error ID 4F530E43505002EF Please report this error at httpjavasuncomcgibinbugreportcgi Java VM Java HotSpotTM Client VM 142b28 mixed mode Java Security Architecture JAR I Classlfoader I Verify VerEl Exception security Java exceptitnrrl Operating System UVa C5216 Spring 2006 Lecture 19 Java Security 3 UVa C5216 Spring 2006 Lecture 19 Java Security 4 JavaVM o Interpreter for JVML programs 0 Has complete access to host machine its just a C program running normally Bytecode verifier ensures some safety properties JavaVM must ensure rest Type safety of runtime casts array assignments Memory safety array bounds checking Resource use policy Reference Monitors UVa C5216 Spring 2006 Lecture 19 Java Security 5 UVa C5216 Spring 2006 Lecture 19 Java Security Program Execution E Program Execution Reference Monitor 9 Monitor Network D39 k 395 Memory SuperSoaker zooc Monitor Program i Speakers Network Disk Memory SuperSoaker 200 UVa C5216 Spring 2006 Lecture 19 Java Security 7 UVa C5216 Spring 2006 Lecture 19 Java Security 8 Ideal Reference Monitor 1 Sees everything a program is about to do before it does it 2 Can instantly and completely stop program execution or prevent action 3 Has no other effect on the program or system Can we build this Probably not unless we can build a time machine Re I weagt Reference Monitor most things 1 Sees Ma program is about to do before it does it 2 Can nstantly and eompeter stop pregram exeeutien or prevent aCtion limited 3 Has Weffect on the program or system UVa C5216 Spring 2006 Lecture 19 Java Security 9 UVa C5216 Spring 2006 Lecture 19 Java Security 10 Operating Systems 0 Provide reference monitors for most security critical resources When a program opens a file in Unix or Windows the OS checks that the principal running the program can open that file 0 Doesn t allow different policies for different programs 0 No flexibility over what is monitored OS decides for everyone Hence can t monitor inexpensive operations Java Security Manager 0 NonIdeal Reference monitor Limits how Java executions can manipulate system resources 0 Userhost application creates a subclass of SecurityManager to define a policy UVa C5216 Spring 2006 Lecture 19 Java Security 11 UVa C5216 Spring 2006 Lecture 19 Java Security 12 JavaVM Policy Enforcment JDK 10 JDK 11 From javaioFile public boolean delele SecurityManager security SyslemgetSecurityManager if security null securitycheckDeletepath Secur tyExecptloh it the delete would v olate the policy teethrowh by delete if isDirectory retum rmdir0 else remm de ete0 What could go seriously wrong with this w csm Svnng 2m e um 19 J seen 3 AppletSecuritycheckWrite d some excepuoh handling code remove initi alizeACLsO ath tilegetCanoniCalPathOi inti riteACLlength in gt 0 or it realPat startswithwriteACLi return throw new Applets ch m tyEXCepti on eckwr te F lle realPath Note no checking if not inApplet Very important this does the right thing w csm Svnng 2m e um 19 J seam currentClassLoader Returns an object describing the most recent class loader executing on the stack Returns the class loader of the most recent occurrence on the stack of a method from a class defined using a class loader returns null if there is no occurrence on the stack of a method from a class defined using a class loader A J A J A w csm Svnng 2m e um 19 J seam HotJava s Policy JDK 117 public class AppletSecurity extends SecurityManager public synchronized void checkDeleteString le throws Security Exception checkWritefile w csm Svnng 2m e um 19 J seam inApplet boo39lean 39inApp39letO return 39inC39lassLoaderO Inherited from javaangSecurityManager protected boolean 39inc39lassLoaderO return currentClassLoaderO null w csm Svnng 2m e um 19 J seam Recap javaioFiledelete calls SecurityManagerCheClltDelete before deleting o HotJava overrides SecurityManager with AppletSecurity to set policy AppletSecuritycheckDelete calls AppletSecuritycheckWrite AppletSecuritycheckWrite checks if any method on stack has a ClassLoader o If not no checks if it does checks ACL list w csm Svnng 2m e um 19 J seam JDK 10 Trust Model When JavaVM loads a class from the CLASSPATH it has no associated CIassLoader can do anything When JavaVM loads a class from elsewhere eg the web it has an associated CIassLoader w csm sprang 2m 7 usz 1 J Sezunty 9 JDK Evolution JDK 11 Signed classes from elsewhere and have no associated CIassLoader I JDK 12 Different classes can have different policies based on CIassLoader Explict enabledisablecheck privileges SecurityManager is now AccessController w csm sprang 2m 7 usz 1 J Sezunty 2n What can go wrong Java API doesn t call right SecurityManager checks 63 calls in java Font loading bug synchronization CIassLoader is tricked into loading external class as internal Bug in Bytecode Veri er can be exploited to circumvent SecurityManager Policy is too weak allows damaging behavior Example Vulnerability Object Creation involves three steps new create new object reference dup duplicate reference invokespecial ltgt calls constructor new 14 ltClass javalangStringBuffergt UP invokespecial 15 ltMethod javalangStringBuffergt w csm sprang 2m 7 usz 1 J Seulnty 22 ucsm SDnnann rlezhne 1 J Seulnty 2J Object Initialization Vulnerability lsdpnet class LSDbug extends SecurityClassLoacler public LSDbug trY this is used but LSDbugS not property catch SecurityException e initialized thisloachlass Bytecode verifier old version didn t make correct public LSDbug int x checks super throws Security Exoeption w csm sprang 2m 7 usz 1 J Sezunty 2a Verifier should be Conservative JVML programs Safe programs Verifiableprograms Slide from Nate Paul39s ACSAC Elk w csm sprang 2m 7 usz 1 J Sezunty 24 Lecture 10 httpwwwcsiiiadc521 Code Red 39brn39 UVa C5216 Spring 2006 Lecture 10 Pointers 3 So why would anyone use C today UVa C5216 Spring 2006 Lecture 10 Pointers 5 C Bounds NonChecking gt gcc o bounds boundsc int main void gt bounds IntX 9 abcdefghijkl Char S4 s is abcdefghij kl User 39nDUt x is 9 getsS gt bounds printf quots is sn s abcdefghijklm printf quotx is dn X sis abcdefghijklmn X is 1828716553 Note your results gt bounds OX6d000009 abcdefghijkln may Vary sis abcdefghijkln depehdlng 0 x is 1845493769 ox ooooog machine compiler gt bounds What else is aaa a few thousand characters crashes shell running time of day etc This is What does this kind of mistake what makes C fun 3900k like in a POPUaF server UVa C5216 Spring 2006 Lecture 10 Pointers Reasons Not to Use C o No bounds checking Programs are vulnerable to buffer overflow attacks No automatic memory management Lots of extra work to manage memory manually Mistakes lead to hard to find and fix bugs No support for data abstraction objects exceptions UVa C5216 Spring 2006 Lecture 10 Pointers Good Reasons to Use C Legacy Code Linux apache etc Simple small Embedded systems often only have a C compiler o Low level abstractions Performance typically 20 30x faster than interpreted Python Sometimes we need to manipulate machine state directly device drivers Lots of experience We know pitfalls for C programming Tools available that catch them UVa C5216 Spring 2006 Lecture 10 Pointers What are those arrows really Stack Heap uva E5216 snnnn 2nnn lean1 In pm s hello Pointers in C Addresses in memory Programs can manipulate addresses directly ampexpr Evaluates to the address of the location expr evaluates to expr Evaluates to the value stored in the address expr evaluates to uva E5216 snnnn 2nnn lean1 In pm Rvalues and Lvalues What does really mean int f void Int S leftsdeofl e evaluates to a location addressl mt t r rightsde of lsal l Name t s t evaluates to a value There is an implicit when a variable is used as an rvalue Pointers In Python an object reference is really just an address in memory Stack 5 022019 uva E5216 snnnn 2nnn lean1 In pm amp oamp intfvoid 39nt 139 uva E5216 snnnn 2nnn lean1 In pm uva E5216 snnnn 2nnn lean1 In pm Parameter Passing in C Actual parameters are rvalues void swap int a int b inttmp 39 aatmp int main void int39 3 Int 4 swap I J The value oh 3 l5 passed not ts locationl 5 9 Wap does nothln uva E5216 snnnn 2nnn lean1 In pm In tm int main inti Parameter Passing in C void swap int a int b e e baatmp void 3 intj 4 swap ampi ampJ39 The value of ampl i5 pa55ed Whlch i5 the addre55 ori Is it possible to define swap in Python w csm spam 2m clean1 In Dummys 15 Manipulating Addresses char s6 sO I expr1expr2 in C iS just syntactic sugar for exprl exprZ 0 55 039 printf s osn s 5 hello w c5216 5pm 2m 7 team in name 15 return count int main void char 51o 1 char 52lo Fun with Pointer Arithmetic int match char 5 char t int count 0 while 5 5 t count 5 t printf quotmamh quotndnquot match 51 52 printf quotmamh printf quotmamh quotndnquot match amp521 amp523 quoth u ello The 0 ls lrivlslblel hohoh ampsZl ampsZ 1 52 1 quotndnquot match 5252 2 match 1 match 3 match 2 w csm spam 2m clean1 In Dummys Beware int value vold nti return ampi l vold call me vold ll ltX 35 l int main Void intW ip value 0 printr p 7 dri ip lp callme 0 princmwp dn ipgt IP 35 But it could reallv be anvthlngl n ma 5pm 2m 7 team in m 14 Obfuscatlng C char s6 s W i r s 1 e 2s ill 5 0 printf s osn s 5 hello n ma 5pm 2m 7 team in m 6 Condensing match int match char 5 char t int count 0 while 5 t count 5 t return count int match char 5 char t i e 5 while 5 t return 5ao5a 1 s evaluates to sm but changes the value of s Hence C has the same value as C but has unpleasant side effects w csm spam 2m clean1 In Dummys Quiz What does 5 s do It is undefined If your C programming contains it a correct interpretation of your program could make 5 spre 1 s 37 or blow up the computer Type Checking in C Java only allow programs the compiler can prove are type safe Exception runtime type errors for downcasts and array element stores C trust the programmer If she really wants to compare apples and oranges let her Python don t trust the programmer or compiler check everything at runtime uva 3216 Spring 2on6 Lecture 1n Pointers 19 uva C5216 Spring 2on6 Lecture in Pointers 2a Type Checking int main void char 5 char 3 printf quot5 squot s hnuexe Windows XP SP 2 Type Checking int main void char 5 char 3 printf quot5 squot s sinnexe e AFDlltaklun Error 39 53 Q The mstvumnn at 39 x mmasr39 refavelted menuv at quotmonomer The mummy mold iiith mad Gldlt an 0K to terminate the mam click an CANCEL to debug the warm caltel Windows 2000 earlier versions of Windows would just crash the whole machine uva 3216 Spring 2on6 Lecture 1n Pointers 21 uva C5216 Spring 2on6 Lecture 1n Pointers 22 Python s List Implementation A Whirlwind Tour httDsvnthhonorqviewthhon trunk0b139ectslistobjectc listobjectc Llst obJect implementation We ll get back to this but you should be convinced fd fSTDC lEADERS zlncfudeltsgjdefhgt that you are lucky to have been else usmg a language With automatic ainclude ltsvstvbes ngt For siz senor memory management so far Ensure obitem nas room for at least newsize elements and set obsize to newsize 1r newsize gt ob size on entrv the content of the new slots at evit is unde ned neab trasn it s the caller s responsiblitv to overwrite tnem wit sane values T e number of allocated elements mav grow shrll lk or stav the same Fallure is impossible irnewsize ltsel a ocate on entrv lnclude Py 39ion h never number of bvtes lt the number of bvtes last allocated the c standard doesn t guarantee ibis but it s nard to lmagine a realloc i ple n ion wnere it wouldn t e ue Note that selrgtobitem mav cnange and even it newsize s less tnan obsize on entrv static int listresizepvtistobiect self pvssizet newsize uva 3216 Spring 2on6 Lecture 1n Pointers 23 uva C5216 Spring 2on6 Lecture 1n Pointers 24 listobject h lypedel slructl PyOblecLVAR HEAD Vector fpoi39nrels to is elements iisrio is obiTammi em Pyobject obiilem obiTern Donian9 space for allomred eemenrs The number currently in use is obisi39ze 39 lnvali39anrs int PyListAppendPyObject op PyObject newitem v if PyListCheckop ampamp newitem NULL Now we know our answer to P51 6 Pytho s 39st retu mplementation continuous is correct rn app1PyList0bject op newitem PyErrBadInternaCa items must nonnaiy nor be NULL except during construction wnen retu m 391 the list is horyer visible oursHe the function harm711 if Pyissizeil allocaIEd PyLlSlOblecl http svri python orgvieWDyl ol lD unklndudellstobject n w csm Staan 2m 7 tenure In pm 25 w c5216 5pm 2m 7 ume n mm 25 appl appl stauc ll lt stauc ll lt app1PyLlstObect seif PyObJect m app1PyLlstObect seif PyObJect m Pyisslzeit ri PWlstJSET IZHseif Pyisslzeit ri PWlstJSET IZHseif assert v i NULL assert v i NULL if n NLMAX if n NLMAX yErLSesmnngxcpver owError yErLSesmnngxcpver owError ririot add more omecs to list ririot add more omecs to list remrn 71 remrn 71 Checks there is Complicated macro if listresizeself n1 in enough space to imiistjesizeeeinnn for memor WWW add 1 more element lemm39ii management needs to PveINCREHv and resizes if PveINCREHv keep 35k f how many PyLisLSELITEWseIfnv PyLisLSELITEWseIfnv references there are to rem 0 necessa ry return 0 object v i i w c5216 5mg 2m 7 ume n mm 27 w c5216 5pm 2m 7 ume n mm 2a Set Item In listobject h Set Item In listobject h PyListObject sefgtobiitemn v Macro trad g safety for speed lypede su ucl PyOblecLVARiHEAD def39quote PYLFSt SET HEMQPI 39I Y Vecrolofpoi39nrels to listelemenfs lisr0i39s obiTammi etc PyLlstObJect op gtoblteml v PyObjecwoleem M a cro text replacement not obiTern Domains space for allocared eiemenrs The numbei 39 I 39cuiienrly in use is obisi39ze procedure calls 39Waiianrs 39 Pyisslleil allocalEd PyListSETITEMseIf n v iPVL S OmeC Now we can be slightly more confident that our PyListobject sef gtobiitemn v answer to P51 4 append is 01 was correct w c5216 5mg 2m 7 ume n mm 29 w c5216 5pm 2m 7 ume n mm an Menu 0 Stack Smashing Attacks and Defenses ISR DeRandomizing MicroVM Lecture 22 Unconven onal Camng http lWWWCSVi g iniaed UC5216 UVa C5216 Spring 2006 Lecture 22 Unconventional Calling u saved ESI m Pathological C Program 839 saved lOid pathological 9V I char a4 quotabcdquot 53 local variable 3 char adr 8 int val 8 3 local variable 2 7 Saved EBP 7 return address lt location of a16 I local variable 1 8bp394 333 3 aval6 0x12 4 aval7 0x00 saved EBP a16 17 lt JMP 2 aval8 0xeb LO aval9 Oxfe 6 return address ammo 0X00 aval11 0x00 gt parameter 1 GbD 8 Q Q int main int argc char argv a parameter 2 GbD12 patholfgllcall g print quot e o nquot 8 parameter 339 Elm 16 return EX1TSUCCESS v UVa C5216 Spring 2006 Lecture 22 Unconventional Calling 3 UVa C5216 Spring 2006 Lecture 22 Unconventional Calling Elle gait mew Evolect guild gebug Idols tndow uelp mv l 39 r pRelease v mammals 333x33 b I 19 39HBX 39v A3 f4355v Palholog 7 am i srrtlur warm gem as Disassemblyl l xl IleEIDlquot A Address pathologica vmd v i lxljl312FEEHZI d0 fe 12 00 D13 7 1 jxomnn5 and snningsev5nsmv chuInEncEv15ual Studio prujecnspath lug1calpathnlugicall 3 2 313171334 138 fe 12 00 p39 39 I3 IDlEFEBE 99 9e 36 DD DDS 1mm pathological u IiixljllleFEBrf UEI DD 00 DD IlelZIDIEFECCI 20 its 12 DD 513 3 willle 2 Qt 10 DD LE char a4 quotabcdquot d0 fe 12 an op at 1 2 Tug32ml l lC39El E le 04 SD 10 00 DE 539 cf 76 a0 ILTIV a gt 61 62 63 6 1 aloud val as 3d c2 1a EIIL O DWIDIE burlt11er momch e4 fa 12 Do 513 h Saved EBP I 7 WW w J retu rn a d d ress 1 4 1 M recurn address lt locatum m a16 v Zl3CIDlZFE 7 2 12 10 DD 335 apen4 0xe4 DD 3 Do a 2 EjillS DXfE 112 I so tlrEll IlelZIlleFE DO I aval16w1w 0x12 lxlllj l FEf39l 05 00 DD DD mic 1l 1110013 FFCIEI Dl UEI 00 DD aval71 v MUD h MI 31 lilzIlZIDlEFFElL 28 Ba 00 DD pr awfulqlu vl IlelZIDlZFFlZIEl 02 DD 00 DD 39 7 L L 7 v lelZDlZFFlZIC 53 65 7392 76 Serv Locals 1 C l5tatllt 69 63 65 ZEI lce Maine l Value l Type Name val 46 232640 9 A n Int 0 PathologicalexelpathologicalQLine22 7 50 61 63 613 Pack 21 SZTEEZZEZEZZESSSTTEW E233 2233iiiillillg iifi fhile252 3V53 32 3 8 a 2 32 00 ee 2 i m 40 f1 0f e2 3 IIleilljliFFZEI 01 DD DU 00 EllDDlZF 3quot 00 DD 00 DD UXCIDIZFF39 98 DU DU 00 El ommzrrc 80 bc de 99 Dlzabi v F lzglzl els Bioll lol vaillv l l calstazk Brealpqinli lm gammawlnm l Output l 7 UVa C5216 Spring 2006 Lecture 22 Unconventional Calling 5 UVa C5216 Spring 2006 Lecture 22 Unconventional Calling void pathological char a4 quotabcdquot char adr int val val 8 ava4 0xe4 ao ava5 Oxfe ava6 0X12 ava7 0X00 a1617 lt JMP 2 ava8 Oxeb ava9 Oxfe ava10 0X00 ava11 0X00 95 on on on u an bode ee DVADl 0040107D mov 00401080 mov edxdword ptr val byte ptr ebpedx30 00401085 mov espebp 00401087 pop ebp 00401088 ret 0012FEE4 jmp 0012FEE4 UVa c5215 Spring 2005 Lecture 22 Unconventional Calling 7 UVa c5215 Spring 2005 Lecture 22 Unconventional Calling 3 Palhulngical properly Pages genngoaooni AttiveR2lease v Elationquot Azuvalwmz v anrgoranoriiwioriager 5 Configuration Pmpeltle A Enable string PWllng No General n ole mronal Rel I No Debugging Enable c Exceptlnl ls vas lensc jl clc smaller Type cnett No 2 eva39 Basil Runllme rnem nerault Ontlwzatlm Huntlmz library singletnreaded lMl WWW struct Membel Alignment Default 0 Code Genevatln r u e V quota Ll ad HE Enable Funtlmnrtev No Enaole Ennanted Instrucllnrl 2 Not Set eutouz rile Erma inrorn Advanted Command line El Llrlker i2 Browse inrarnation 393 said Events 7 E r c to 5 id st 3 w D39 2 W V hezkfal laiulrer averluns useful for losing hackahla lanphnla on internet sewers J P Y gt lgrlaredfnrpmjezls using managm extensions 65 GS Option The compiler injects checks in functions with local string buffers or on X86 functions with exception handling A string buffer is defined as an array whose element size is one or two bytes and where the size of the whole array is at least five bytes or any buffer allocated with M httpmsdn2m crosoftcomenUSIibraryBdbf701cVS80aspx cancel Apply Help UVa C5216 Spring 2006 Lecture 22 Unconventional Calling 9 UVa CS216 Spring 2006 Lecture 22 Unconventional Calling 10 With GS void pathological char a5 quotabcdquot Security Cookies void pathological 00401030 push ebp 00401031 ebpesp 00401033 sub esp14h 00401036 mov eaxdword ptr securitycookie 408060h 0040103B mov dword ptr ebp8eax 3 o lt 0040109B mov eaxdword ptr val 0040109E mov byte ptr ebpeax50 004010A3 mov ecxdword ptr ebp8 004010A6 call securitycheckcookie 40111Eh 004010AB mov espebp 004010AB pop ebp 004010AE ret UVa C5216 Spring 2006 Lecture 22 Unconventional Calling 11 UVa C5216 Spring 2006 Lecture 22 Unconventional Calling 12 A cookie ebp return address StackGuard implementation ebp canary u be a 39u Dx lzirii m 52 55 D2 phU return address UVa CS216 Spring 2006 Lecture 22 Unconventional Calling 13 Cookie Checking void decspecnaked fastcall securitycheckcookieDWORDPTR cookie x86 version written in asm to preserve all regs asm cmp ecx securitycookie 0040111E cmp ecxdword ptr securitycookie 408060h jne failure 00401124 jne failure 401127h 00401126 ret failure jmp reportfailure 00401127 jmp reportfailure 4010EDh UVa c5215 Spring 2005 Lecture 22 Unconventional Calling 14 Does it work vo d patholog cal char aS quotabcdquot char adr int val printf quotHeonquot va 1 return address lt location ofal6 ava4 0xe4 ava5 Oxfe ava6 0x12 ava7 0x00 a1617 JMP 2 ava8 0xeb ava9 Oxfe ava10 0x00 ava1l 0x00 UVa CS216 Spring 2006 Lecture 22 Unconventional Calling 15 Works in Practice 0 Most attacks can t skip over cookie Must fill up buffer instead of directly assigning to locations 0 Lots and lots of other proposed defenses UVa CS216 Spring 2006 Lecture 22 Unconventional Calling 16 An Instruction Set Randomizing MicroVM UVa CS216 Spring 2006 Lecture 22 Unconventional Calling 17 l save worm address in ebpl i move stack frame pointer l l WormIP e 0 lcoy worm code into buffe l update WormIP l i save M croVM 39sters l l load worm registers l MicroVM Learned K B 76 bytes of code ey Ytes 22 bytes for execution 2 bytes to avoid NULL 100 bytes is enough gt 99 of the time 22byte worm execution buffer save worm registers l load MicroVM registers l ijm to read next block l saved re isters Worm code must be coded g in blocks that fit into worm COde execution buffer pad with noops so instructions do not cross block boundaries host key masks guessed target masks other worm data UVa CS216 Spring 2006 Lecture 22 Unconventional Calling 18 Lecture 2 Orders of Growth httpwwwcsvirginiaeduc5216 Predicting Program Properties UVa C5216 Spring 2006 Lecture 2 Orders of Growth 3 Predicting Running Time Experimentally measure how long the program takes on particular inputs Generalize extrapolate to other input sizes Analytically figure out how the amount of work scales with the input size Understand what the program does Need to combine with experimental results on some inputs and analytical understanding to make good predictions UVa C5216 Spring 2006 Lecture 2 Orders of Growth 5 Menu Predicting program properties Orders of Growth 0 2 Course Survey Results Everyone should have irecefivessd an email y it Infornmij39ngg you of r 1 iartnzer Giving the section foo m locf39aiti39isorns Explai39nfin that PSI i izss now due Monday la n UVa C5216 Spring 2006 Lecture 2 Orders of Growth 2 Sindee Cavalier Daily We ve tried to take steps to try and TDDAY SPAPER NEW news Siude t5 mitigate the problems by moving Rep39acem39 tax administrators off the system making lure one time thou iCOMICS A T88 m OTHER WEEKLIES H nithamp5lxuai Ashley Simp n Cavali Students cross the Student nforrnetion some improvements to the codequot Webb said Unfortunately to see W semes r 33 i SN m whether it works students need to be u 3 say e s ARCHWES fr m nal39 in rinc quot 39 392 959 on the system 3th i A aWEhbus uui p u t an uuug um u loll1W i roving the pro ram RESUURCES Corrections We re tried to take steps to try and mitigate the problems by moving administrators offthe system making Elf 39f39ei ws some improvements to the codequot Wele said quotUnfortunately to see whether it works students need to be the D on the system Students said this is a major issue and comes at a crucial time when they need the services oflSlS the 7 Poll wwwww al most citinng 39 Thimtyear coinage mi m Fm h ir hnnl Mnam girl hn an Hthch tn nrint a My of hi nrnrln rnnnrt that i Webmaster i he needed for an applic A A i A Cava lier ally lF ri ay Ja n httpg l wwwlectat la l39ierdai39lytcomCWA rticlea sp 31Di2 548 1 UVa C5216 Spring 2006 Lecture 2 Orders of Growth 4 Order Notation Four notations0f 52f of f 0 These notations define sets of functions Functions from positive integer to real 0 When we say Algorithm A is 0n we mean running time of A e 0 n where n measures the input size to A UVa C5216 Spring 2006 Lecture 2 Orders of Growth 6 m0 dMMmM MEW o roommommmmo r t I c u More formal definition coming soon mecwmm inmmm mmmemmmiw WWWMWW e ommmmommmm 1mm Mmmo 0111501631logo423 hmms HmoMMMn Ohmms I 1mOmomm mme mmm WMWWMWWMM 1131111111 constants 119111111 iaieizio ii MRM owMowWWMe WWHMM1 WWW memm M Noromaiier vinaioand 10 39 wepidgoimiorbigenoudii WaSZlSqu mLommlodusof mw i 9 WaSZlSSJr39nqmLemlmiesof mw i 10 Question a is false Prove by CounterExample omowooowoooo mmmme eWMNmmm Mom oommmmmi iWW emmmmmwM Wmmmmo Mom left as problem for Exam 1 MWWWWNMWW eooommmmmomo Pick i111 12111115112 goo3 momooooo mmnmme omommmmmm pMMwMMwmommm oi ogii ior a vaiues 112111 WatSZlSSm mumeowomwo 11 WaSlesor39nqmLemmlmiasof mw i 12 b is true Intuition hummeWmhmm mmmemmm mummmmmumm Wmth mummmuhu thh SMMWWWWMMWW MWMWMWMWWM gngtfn50forsomemfmltgm b Proot by Contradiction hummeWmhmm WWWWWMMW ihmmmmmMmmms mMmmmmde Wmm ahmnmmmmm mmmuuummm WMWMMmuMWw prmmWMMW ummw WaSZlSSm IDS Luciana 2 MMGMI 13 Wasncsmgmumaoumuouun 14 b Proot by Contradiction hhMWMMWmhmm uhmehmn smmnmmmm hmmdmmmmah From 1 doingsuohthatidngtn0fnSohn From 2 do1 in such thatiingtn1gngtc1idn Combinlndoidolduzsuohthatidmu2 ihhdgthdhhd Noteloz nnaniugh T rummmuuwmr nmhmehwmmmw Lower Bound 9 Omega do is ii g at means There are positive constants c and such that WC it for all nZnO Differenoe from 0disnas uuacsznosm mWnl dmof ruw r 15 Ilda llswrirgmLednrrumdusufdmwh 16 hidden v WaGZldwr39nnmLudurulihdusof mwh 13 Survey Results Summary See course web site for more detailed results VzESZISSvnuq mam 2Drderxol mwlh 19 Honor Disadvantage Do you feel you are at a disadvantage if you follow the course honor policy strictly 3969 n0 1 hope the majority answer 11 Yes here will help convince the 11 yes answered they are not really at a disadvantage Long term being honorable is never a disadvantage VzESZISSvnuq mam 2Drderxol mwlh 21 Honor Questions How much faith do you think we should put in the honor system for this class 30 Should have complete trust in honor system 7380 43 Enough to have takehome exams 6 A little but don39t trust takehome exams 1 Don39t trust the students at all need to police everything IExam 1 will be take home VzESZISSvnuq mam 2Drderxol mwlh 2n Honor Reporting If you observed a classmate cheating on a take home exam what would you do 36 Report the student anonymously to the course staff 20 Confront the student e student to the course staff 9 3 nItIa ge M 0 Course Pledge disallows this now If you can t han let is don39t sign the course pledge and take a different class VzESZISSvnuq mam 2Drderxol mwlh 22 Course Pledge Read this carefully you are expected to know it and follow it Only pledge you need to sign this semester Requires No lying cheating or stealing Helping your classmates learn No toleration of dishonorable behavior Helping the course staff improve the course Programming Self Rating 4 among best 26 above average 41 about average 8 a little below far below The programming you will do in this class is different enough from w at you have one previously that you probably don39t really know Everyone should be confident you will do well in this class You don39t need to be a super code hacker to ace this class VzESZISSvnuq mam 2Drderxol mwlh 2a VzESZISSvnuq mam 2Drderxol mwlh 24 Lecture 11 Managing Memory 7 hH39n39 I n n l infnrmar In httpwwwcsvirginiaeduc5216 Physical Memory l v a 1901 WWW Vacuum Magnetic Capacitor TUbe Core store charge DRAM UVa CS216 Spring 2006 Lecture 11 Managing Memory 3 StaticDyna mic Allocation 0 Static space required is known before program starts at compile time 0 Dynamic space required is not known before the program starts Can be placed on either the stack or the heap UVa CS216 Spring 2006 Lecture 11 Managing Memory 5 Levels of Abstraction Python a helloquot Ox80496f8 Ox80496f9 C a Ox80496f8 OX80496fa Ox80496fb OX80496fc Ox80496fd 0 Digital 011010000110010101101100 Abstraction 011011000110111100000000 UVa CS216 Spring 2006 Lecture 11 Managing Memory 2 Memory in C Stack Heap o Managed by 0 Managed by compiler programmer automatically explicitly 0 Lifetime is 0 Lifetime is determined by controlled by program scope programmer Cannot outlive Lives until freed by procedure return program UVa CS216 Spring 2006 Lecture 11 Managing Memory 4 malloc void malloc sizet size Returns an untyped pointer Size in bytes can point to anything Malloc returns an address that is the location of at least size bytes of previously unused memory and reserves that space Or returns null is there isn t enough space UVa CS216 Spring 2006 Lecture 11 Managing Memory 6 Memory Allocators Lifeti me Scoped Unlimited Known local variable glo39PBquot 53933 m declaratons Var39ab e n declarauons 17 unknown alloca malloc alloca like malloc but on the stack not heap rarely used iiva csm svnnq 2m 7 tenure n Managng Menary String Concatenation lnclude ltsmllb hgt lnclude ltstring hgt lnclude kilo hgt irt main Ont argc char Wargv ll ltl Oi char result d39lar tlt malloc slzeof tresult result o Whlle a lt argc d39lar s char tlt malloc slzeof as strlen resut strlen argvm 1 strcpy 5 result strcat S argvii s Some serious problems with this returno we ll discuss soon l prihtf cmcatehatim yam result iiva csm svnnq 2m 7 tenure n Managng Menary Malloc Example char 5 char malloc sizeofs n HJ H4 type cast malloc returns void cast tells compiler we are using it as a char sizeof operator Takes a type or expression evaluates to the number of bytes to store it iiva csm svnnq 2m 7 tenure n Managng Menary Concating Strings char 5 char malloc sizeof s strlen result strlen argvi 1 strcpy 5 result strcat s argvi Why is the parameter to malloc what it 7 iiva csm svnnq 2m 7 tenure n Managng Menary string functions int strlenchar 5 e returns number of chars in 5 not counting 39 amr null termln char strcpychar 51 const char 52 7 Copies the strin pointed m by 52 including the terminating null bym mm the space pointed m by 51 If copying takes place between objects that overlap the behav or is undefined char strcatchar 51 const char 52 a appends a copy of the string poinmd to by 52 including the terminating null byte to the en of the string pointed o by 51 The initial byte of 52 overwrims the null byte at the end of 51 If copying takes place between objects thatoverlap the behavior is undefined iiva csm sunng 2m 7 tenure n Managng Menarv 11 Concating Strings char 5 char malloc sizeof s strlen result strlen argvi 1 strcpy 5 result strcat s argvi We need enough space for s to hold all the chars in result all the chars in argvi and the null terminator iiva csm svnnq 2m 7 tenure n Managng Menary Memory Lifetimes include ltsmiib hgt include ltsmrig hgt include ltsmio hgt int main Grit argc d39iar Wargy ii iti Oi char result d39iar X malloc sizeof result result o while a lt argc l d39iar s char X malloc sizeof as strleri resut sirleri argym 1 sircpy s result street 5 argvlei resut s i printf concatenation View result reclaimed 7 remm 0 When is space allocated by malloc uy csm some 2m 7 tenure n Moneomo Memory Storage allocated by malloc is reserved forever void freevoid ptr The free funct o m t IS made hrrn imlude ltsmiib hgt int main Grit argc d39iar Wargy l ii iti 0 char result d39iar X malloc sizeof result result o while a lt argc l d39iar s char X malloc sizeof as strleri resut sirleri argym 1 strch s r ult ar free result l printf cmcatenaum sn result return 0 Plugging Memory Leaks uy csm some 2m 7 tenure n Meneoo Memory References char result char malloc sizeof result while i lt argc char s char malloc strcpy s result strcat s argvi result s i scope of s is closed should we frees first No result now references same storage uy csm some 2m 7 tenure n Moneomo Memory Reclaiming Storage Give it back by passing it to free loco been deallommd by a call to free the behavior is undefined ion shall cause the space pointed to by ptr o be ma uy csm some 2m 7 tenure n Moneomo Memory Memory Leak There is no reference to allocated storage It can never be reached It can never be reclaimed Losing references Variable goes out of scope Variable reassigned uy csm some 2m 7 tenure n Meneoo Memory References char result char malloc sizeof result while i lt argc s char malloc char strcpy s res l 39 strcat s argvi after this assignment no way to reach storage result previously pointed to uy csm some 2m 7 tenure n Moneomo Memory indude ltstdiib hgt C Vs 39 0 n C VS I 0 n 12333 EEC import sys int main int argc char argv ht nah Ontargcr char Wargw ltchar resuit6 heiio res m ii iti 0 Whiie strienresuit lt 1000000000 dwar hesuit Char K maiioc sizeof chesuit for a rg In sy5argv Wesut 0 r chars char maiioc sizeof 5 2strien resuit 1 Wh ewam res arg strcpys Eesuit r it prlnt res strcats resu char 5 dwar maiioc sizeoms limitsth res quothelloquot smen resuit strien argvm 1 39 39 imp syurim mama while enres lt 1000000000 ree res t strcatsargvi res resuit S f gt time python concatpy printf Comcatenanon quotsz resuit reiLrn 0r 446u 11705 94004 w csm smg 2m 7 tenure 11 Managing Memory lg 7 mm mm 2n appl stauc ii it Python 5 List Im ple mentation apD1PvListObJectseifr onmectm Pyissizeit n PwstjETjizaseif assert v NULL if n N LMAXM htt 39 svn39 thon 39 or Vlew thon PyErrjesmngwaxcpver owError trun k 0 bjectsllistobject c cannot add more objecs to hst return 71 if Iistresizeself n 1 1 return 1 PLINCREHv PvListjEi IIEWseIf n v return 0 1 7 mm We 21 7 mm MW 22 I ISt res I 26 This overraiiocates proporuonai to the hst Size making roorn for growth The overraiiocauon is miid out is enough t g static ii it over hstresizepytistooect seif Pyissizeit newsize pooriyrperformmg system reaiioco addmonai we iinearrume The growth pattern is 0 4 a 15 25 35 45 so 72 EB PyObJect item5 sizeitnewiaiiocated neWJHocated newsize gtgt 3 newsize lt 9 9 3 s newsize issizeitaiiocated seifrgtaiiocated ifi ieWSize 0 neWJHocateg 0 Bypass reaiioco when a previous overaiiocauon is iarge enough items seifrgtob7item ifaiiocated gt newsize ampamp newsize gt aiiocated gtgt 1 ifnewauocateg lt sizet0 sizeoKPyObect assermseifrgtob item i NUU H newsize 0 PvMem 7 REsIzEatems onbject newiallocated seifrgtobisize neWSiZe 0 return exprl gtgt expr2 010000 gt Value Is value of exprl um yErLNoMemoryO n retur with bits moved right gmob tem at m 001000 vaue of exprz times seifrgtobsize newsiz39e Seifrgtaiiocated newiaiiocated x gtgt 1s Similar to x 2 mm w csm smg 2m 7 tenure 11 Managing Memory w csm smg 2m 7 tenure 11 Managing Memory PyMemResize ade ne PyMemRESIZEp type n p type PrMemakEALLOC p n si2e0ftwe PyMemMALLOCO means mallocl Some systen39s would return NULL for mallocO which would be treated as an error Some platforms would return a pointer with no memory behind it which would brmk pymalloc To solve these problen39s allocate an extra byte de ne PyMemMALLOCn mallocn n 1 de ne PyMemREALLOCp n reallocp n n 1 PyMemRESIZEitems Pyobject newallocated i tems PyObject realloc items newallocated sizeofPy0bject quotVa csm Spnng 2m 7 lezmre 1 Manama Mammy 25 realloc void reallocvoid ptr sizeit size The realoc function changes the size of the memory object pointed to by ptr to the size specified by size The contents of the object will remain unchanged up to the lesser of the new and old sizes If the new size of the memory object would require movement of the object the space for the previous instantiation of the object is freed If the new size is larger the contents t e newly allocated portion of the ob39ect are unspecified If size is 0 and ptr is not a null pointer the object pointed to is freed If the space cannot be allocated the object remains unchange http www opengroup orgonllnepubsOO790E799Xshrealloc hunl quotVa csm Spnng 2m 7 lezmre 1 Manama Mammy 2s realloc is risky lntrnaln lrltargc char al gv char s a char rnalloc slzeofs a char t t l Strcgy 5 hello lll l 394 schar r alloflsl15M 5 s hello 20a80 20a80 ti H h SDDJDJ H39S39Squot39 s hello 20e88 20a80 O strcpy S eers prlrltf s aas t srl s t s cheers t he s hello 20a80 20a80 s hello 20a80 20a80 s cheers t cheers quotVa csm Spnng 2m 7 lezmre 1 Manama Memm y 27 realloc void reallocvoid ptr sizeit size The realoc function changes the size of the memory object pointed to by ptr to the size specified by size The contents of the object will remain unchanged up to the lesser of the new and old sizes If the new size of the memory object would require movement of the object the space for the previous instantiation of the object is freed If the new size is larger After a realloc any use of the original location of ptr has undefined behavior quotVa csm Spnng 2m 7 lezmre 1 Manama Memm y 2a Running time of realloc oTime to reserve new space 01 oTime to copy old data into new space 7001 where n is the size of the old 3950 how can Python s list append be 01 quotVa csm Spnng 2m 7 lezmre 1 Manama Memm y 2g statlc lnt llstreslzePyLlstoblect self Pyisslzeit newslze Pyobject ltem5 slzet newiallocated Pyisslzeit allocated selregtallocated Thls overaallocates proporuonal to the llst slze rnalltlng roorn for aggltlonal rowrh The overaallocauon ls mlld but ls enough to give llnearaurne arnoruzeg behalllor over a long sequence of appengso ln the presence of a poorlyeperrorrnlng system realloco The growth pattern ls o 4 a 15 25 ocat new all newslze gtgt 3 newslze lt 9 2 3 a newslze lrnewslz newallocateg o lterns se 0 l eml llocated lt Nrslzegm slzeorrpyoolect m lrnew PyMemiRESIZEUtems Pyobject newiallocated else lterns Nuu lrlterns ULL PyErlNoMernory return 1 selfrgtob7ltern lterns selfrgtob7slze l leWSlZe selregtallocated newiallocated return 0 quotVa csm Spnng 2m 7 lezmre 1 Manama Memm y an Lecture 9 w LowLevel P ro g ra m m i n g 1e Mammals Observe Them From a Safe Distance Marine Mammals are Wild Animals and Can and Keep Pels on a Li lSl b 39 Dangcioilsl a ions t he NlVlFS Enforcement HOIllllE 1 8 O853 1964 httpwwwcsvirginiaeduc5216 Menu Complexity Question LowLevel Programming Exam 1 Out Wednesday Due Monday 1101AM Covers everything through Lecture 8 Expect questions on order notation algorithm analysis lists trees recursive programming dynamic programming greedy algorithms Not on complexity classes Lecture 8 UVa CS216 Spring 2006 Lecture 9 LowLevel Programming Problem Classes if P 2 NP Sequence Alignment 0n2 How many problems are in the n class infin te How many problems are in P but not in the n class infinite How many problems are in NP but not in P infinite NPComplete Note the NP Complete class is a ring others are circles Interval Scheduling Subset Sum n 10g n 3SAT UVa CS216 Spring 2006 Lecture 9 LowLevel Programming 3 Is it ever useful to be confident that a problem is hard UVa CS216 Spring 2006 Lecture 9 LowLevel Programming Knapsack Cipher Merkle amp Hellman 1978 0 Public Key A 611 a2an Set of integers Plain Text x1xn x O or 1 Cipher Text 11 s 2 m i1 UVa CS216 Spring 2006 Lecture 9 LowLevel Programming 5 Subset Sum is Hard Given s and A it is NPComplete to find a subset ofA that sums to s Need to make decrypting each for recipient with the private key UVa CS216 Spring 2006 Lecture 9 LowLevel Programming Superincreasing Set Knapsack Ciphers P1aP2pn A superincreasing sequence Vaues M and W Pick a1a2an is a superincreasing sequence i l di gt Zaj M gtZn1bi 391 11 J GCDMW1 How hard is subset sum ifA is superincreasing PUbl39C Key 1 2quot n 611 E biWm0dM Flawed Security Argument Levels of Abstraction Program Real World Problem Subset Sum is NPComplete 0 Breaking knapsack cipher involves solving a subset sum problem 0 Therefore knapsack cipher is secure Flaw NPComplete means there is no fast general solution Some instances may be solved quickly Note Adi Shamir found a way of breaking knapsack cipher 1982 HighLevel Program PIJOM 935Alid Virtual World Machine Instructions Physical Processor I From Lecture 3 UVa C5216 Spring 2006 Lecture 9 LowLevel Programming 10 UVa c5215 Spring 2005 Lecture 9 LowLevel Programming 9 CrossingLevels Python Program I C Program L as m39mijns liar Programming Languages UVa C5216 Spring 2006 Lecture 9 LowLevel Programming 11 UVa C5216 Spring 2006 Lecture 9 LowLevel Programming 12 Fortran 1954 IBM Backus Algol 1958 LISP 1957 BASIC 1963 CPL 1963 U Cambridge SCheme 1975 Combined Programming Languag Simula 1967 BCPL 1967 MIT Basic Combined Programming Language ABC 1980 B 1969 Bell Labs Smal alk PARC c 1970 Bell La III 83 Bell Labs Objective C Python 1990 v I Gu do van Rossum Programmlng Languages Java 1995 Phylogeny Simplified UVa C5216 Spring 2006 Lecture 9 LowLevel Programming 13 I Em amts innIT All ll A l l l 4 1 397 1 395sz I39oma l I I mm 139 Jamais Jamais Jamais from Harmonice Musices Odhecaton A Printed by Ottaviano Dei Petrucci in 1501 first music with movable type Why so many Programming Languages UVa C5216 Spring 2006 Lecture 9 LowLevel Programming 14 TZQ 1 av Innu 11761 39 4 Il II ll quot39 Inn nu moms I l IIII Al 23 M 53 451 1 41 7 7 4 7 l3 5 at W L yl awl i t quot 391z LTx39 3971 J Jamais Jamais Jamais from J s Bach Coffee Cantataquot Harmonice Musices Odhecaton A Bwv 211 1732 1501 www npjcomhomepageteritowejsbhandhtml 1amp1 r4236 UVa C5216 Spring 2006 Lecture 9 LowLevel Programming 15 UVa C5216 Spring 2006 Lecture 9 LowLevel Programming Modern Music Notation Roman Haubenstock Ramati Concerto a Tre John Cage Fontana Mix httpwww 39 39 39 i uu UVa C5216 Spring 2006 Lecture 9 LowLevel Programming 17 4 55 I m MY um I cm xm u mamm6 W TABET momenta Ian was 1397 MINES uxummus sari mm WEBS W smsmmam mm msm K We ns Emma ATWI1YAWT 1231559 m mu VAS I SS IMP his 1185 mm 143216 ha rum RWV w mmmm19rwnm mm m vwl v oi ms w oria39nli lms 1 Dmi THCET MBJXEW um m m magmas Panama1qu MY II Mthm AL limos mm M 1m WM 11 n men15m or WWW 30317315111quot nlo 5mm t was mam rmramsv 51 my 31 m mmmmmmmvmmmm 0711112 FM man KRMEH TNE ET UVa C5216 Spring 2006 Lecture 9 LowLevel Programming Thought and Action 0 Languages change the way we think Scheme think about procedures BASIC think about GOTO Algol Pascal think about assignments control blocks Java think about types squiggles exceptions Python 0 Languages provide abstractions of machine resources Hide dangerousconfusing details memory locations instruction opcodes num er representations calling conventions etc Abstractions 0 Higher level abstractions Python Java BASIC Easier to describe abstract algorithms But cannot manipulate lowlevel machine state How are things stored in memory Opportun ties for op miza on lost 0 Lower level abstractions C C JVML MSIL Assembly Harder to describe abstraction algorithms Provides programmer with control over low level machine state w csm san 2m 7 lentquot a lnwrhevel Mqrammnq 19 w csm san 2m 7 lentquot a lnwrhevel Mqrammnq 2n Biggest Single Difference Memory Management High level languages Python Java provide automatic memory management Programmer has no control over how memory is allocated and reclaimed Garbage collector reclaims storage Low level languages C Assembly leave it up to the programmer to manage memory Fortran 1954 lBlVl Backus Algol 1958 LISP 1957 BASIC 1963 CPL 1963 u Cambr dge SCheme 1975 combined Programming Languag Simula 1967 ESch 1967 MIT mateywa quumm m WW ABC 1980 B 1969 Bell Labs Smal 19 c197o Bll I 83 Bell Labs Objective c a k 1 PARC Python 1990 o 0 van Rossum Programmin Langua es Java 1995 Phylogeny Simplified w csm san 2m 7 lentquot a lnwrhevel Mgrammng 21 w csm san 2m 7 lentquot a lnwrhevel Mgrammng 22 C Programming Language Developed to build Unix OS Main design considerations Compiler size needed to run on PDPll with 24KB of memory Algol60 was too big to fit Code size needed to implement the whole OS and applications with little memory Performance Portability Little if any consideration Security robustness maintainability C Language No support for Array bounds checking Null dereferences checking Data abstraction subtyping inheritance Exceptions Automatic memory management Program crashes or worse when something bad happens Lots of syntactically legal programs have undefined behavior w csm san 2m 7 lentquot a lnwrhevel Mqrammnq 2a w csm san 2m 7 lentquot a lnwrhevel Mgremmng 24 Lecture 15 Compression httpwww r Iirnini armr 71a Menu Garbage Collection Puzzle Encoding Huffman LZW GIF Representing Numbers Fighting Finalizers finalize method in javalang0bject Cass can override It is called when GC determines the object is garbage before collecting it x NULL X a E GC afnalze 0 WMMLM Mm 3 I bfinalize Finality Class A class B B p A rr39 void finalize a new A P th39s ap new 30 apr a ap NULL GC bfinalize aptoString w mm mm 2m 7 mm IS Nunhas Problem due to Paul Tyma Google Encoding Huffman Encoding We proved there is no better encoding o Prefix encoding can divide coded message into symbols without looking ahead oOnetoone mapping SymbolaBits o Fixed mapping Can we do better without these constraints LempeIZivWench LZW Terry Wench refined the L Z scheme Fixed length typically 12 bits codewords Dictionary maps each codeword to text Greedy scheme for building dictionary w csm sum1 2m 7 mm 15 Nun ers 5 w mm mm 2m 7 kn IS Nunhas LZW Encoding Algorithm def LZWEnoode s w n res n dictionaryinitiaize code for each alphabet symbol in s ifdictionaryconlains w k i else need to do sorrevhing if dictionaly is Full dictionaryappend w res res dictionary nd ww is already ll l dlctonary no need to send dlctonary to decodel uv csm sbuuu zuub r lezmre IS Numers 7 GIF Graphics Interchange Format developed by Compuserve 1987 Algorithm Divide image into 8x8 blocks Find optimal Huffman encoding for those blocks Encode result using LZW How is GIF different from JPEG uv csm sbuuu zuub r lezmre IS Numers What s wron with GIF s Divide image inm 8x8 blocks s Find opu39mal Huffman encoding for those blocks s Encode result using sz 1978 L2 patenmd by Sperry 1984 June Welch s article on sz 1984 July Unix compress implemented using sz 1987 Compuserve develops GIF Graphics Interchange Format image format used sz butdidn t know t was patented GIF becomes popular 1994 UnisysCompuserve decide that developers who implement sz including in GIF will have m pay a licensing ee I 2003 LZW patent expiredPNG 615 Not GIFquot Compre55lon Ba ke off Declaration of Independence Original 8586 Huffman PS4 Compress LZW Gzip not LZW Random Characters Original 10000 Huffman PS4 Compress LZW Gzip not LZW This is quite surprising 5123 60 4441 52 3752 44 951 10000 file unchangedquot 8800 uv csm sbuuu zuub r lezmre IS Numers LossyLossless Compression Lossless Compression uncompress compress 5 S Lossy Compression uncompress compress 5 similar to S For images sound video lossy compression is usually okay For computer programs declarations of independence email only lossless compression will do uv csm sbuuu zuub r lezmre IS Numers uv csm sbuuu zuub r lezmre IS Nuubees 11 Representing Numbers uv csm sbuuu zuub r lezmre IS Nuubees N M C5216 Lecture Notes on Number Systems Question Which is the bigger number 5 3 2 ans 5 Alternative question Which is ve ve V cinq 101 ans none The point These are all names of the abstract notion of veness We can invent LOTS of other systems to name numbers NUMBER NUMERAL Positional Polynomial Number Systems Example decimal 346 3 100 4 10 61 general radix R or base R n Integers dndnild0 Z aligtltRi i 0 and Reals dndn 1d0 0 dildizdim Radix Point The d s are generally 0 l R Common notation Do some examples binary ternary octal hexadecimal Conversion Radix R to Decimal Compute the expansion 71 dRquotd0R0 n Lecture Notes on Number Systems Last Edit 4600 Decimal to Radix R n 11 an Algorithm Divide succesively by R Note remainder at each step order of digits is lsb to msb 71 0 n le With rema1nder d0 Radix R1 to RadiX R2 R1 to decimal to R2 4 Systems of Special Interest Binary base 2 Easy for computers Octal base 8 Easier for people Hexadecimal base 16 Easier for people Show conversion between all of these Emphasize heX numbering 0 9ABCDEF 5 Integer Representation in Real Computers Issues Fixed Size Negative Number Representation A Fixed Size The XXX is a 16bit vs 32bit computer If word size is n bits there are 2n possible bit patterns so only 2n possible distinct numbers Implications Cannot represent all possible numbers Must use some of these bit patterns half to represent negative numbers B Negative Number Representation i sign magnitude the obvious one reserve one bit for the sign rest of bits are interpreted directly as the number C5216 Lecture Notes on Number Systems Last Edit 4600 I magni u e I nl sign bit I 0 gt 2n l I 0 gt 2nl I 0000 01111000 1111 Notes Two 2 zeros generally bad Arithmetic costly we ll see I radix and radix 1 complement also called r s and r l s k represented as Rnk example base 10 10 s complement n2 3 3 3 102 3 97 o 491 50 1 I 0 491 50 99 Negation is simple Complement every digit and add 1 lOOk99kl Example R10 38 99 38 1 61 1 62 629962138 2 s complement special case k 2n k I 0 gt 2n l I 2nl gt 1 I 0000 01111000 1111 C5216 Lecture Notes on Number Systems Last Edit 4600 Negation Complement means ip the bit so ip every bit and add one Example R2 n8 9510 0010111 ip 1101000 add 1 1101001 95 Note that renegating gets us back to the original Notes One zero this is good Arithmetic easy we ll see iii excess B Represent k whether or as k B B 1 0 RnB1 0 B l B Rn Note allows asymetric range 6 Arithmetic 0n Positional Systems A General Arithmetic We all know how to do arithmetic in radix 10 using carries 854 0 l 2 9 0 00 10 20 90 1026 1 10 20 30 01 2 9 ltsumcarrygt Same in other radices just use a di erent table Example Our hero binary OlOOll Carryin OOlOll 1 011110 0 l 0 l 0 00 10 0 10 01 1 10 01 1 01 11 B Sign magnitude Add the operands then check the signs and the magnitudes of the operands to deter mine the sign of the result It s a pain and expensive to do in hardware lots of comparisons and control required C5216 Lecture Notes on Number Systems Last Edit 4600 C 2 s complement Addition and subtraction are easy Add the two numbers and throw away the carry Don t need to worry about the signs of the operands Examples Assume 4bit computer rst bit is sign bit 1000 8 1101 3 1111 1 0001 1 0010 2 0001 1 1001 7 1111 1 10000 0 D Over ow i Demonstration OYThat s 0110 6 Negative Olll 7 1101 13 We call this OVERFLOW The number 13 is not representable in a 4bit 2 s complement computer Question Does the problem go away if we have more bits Answer Nope not in general though we could safely add 67 with more bits ii Detection Examine the signs of the operands and the result If signs of operands are diiTerent cannot have over ow If sign of operands are the same and the sign of the result is diiTerent over ow These checks are easy to do in hardware 7 Representation of Other Scalars A Alphanumeric characters 8bit byte 7bit ASCII codel a 6116 A 4116 3B16 Z 7A16 Z 5A16 2016 B Real numbers i Fixed Point Given 11 bit number radiX point is xed at some bit f So f integer bits and nf fractional bits I ASCII American Standard Code for Information Interchange CS216 Lecture Notes on Number Systems Last Edit 4600 CS216 fraction inte er Fixed Point not used because of limited range ii Floating Point Computer analog of scienti c notation Instead of 547764 547764 102 IEEE standard speci es number of bits for fraction mantissa and exponent plus a bunch of other stuff IEEE Flavor of Floating Point adix point mant1ssa siEn exp i 39 h nl idden bitleading bit Examples Assume 12 bit computer 7 8 w hidden mantissa 4 exponent excess 8 O 1010 1010000 exp 108 2 mantissa 1101 1 12 18 1625 16252265 1 0101 0110000 exp 5 8 3 mantissa 1011 1 14 18 1375 L3751 23OJ71875 Notes ow 4 sizes single single extended double double extended exponent is excess B generally normalized hidden bit is always 1 denormalized numbers possible for very small numbers exponent is minimal and fractional bits are shifted right Continued shifting causes gradual under hidden bit not stored special bit patterns in exponent for NotaNumberNaN and in nity Lecture Notes on Number Systems Last Edit 4600

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "I made $350 in just two days after posting my first study guide."

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.