Cyclone - University of Maryland at College Park
Contents
1. weaker guarantee less burden e Cqual user defined qualifiers lots of inference e SFI Wahbe Small sandboxing via binary rewriting Related work higher and lower Future Work e Adapted extended ideas e Tracked pointers sometimes painful want polymorphism ML Haskell amp regions Tofte Talpin Walker et al Better inference e g for alias safety via dataflow Java Richer API restrict autorelease cer eer e Prevent leaks unique and reference counted pointers e Specified aliasing for doubly linked lists etc e Concurrency e Safe lower level languages TAL PCC engineered for machine generated code e Vault stronger properties via restricted aliasing Conclusions More Information e High degree of control y e Cyclone homepage e Sound mechanisms for low level control Checked pointers for spatial errors Variety of techniques for temporal errors e Region based vs object based deallocation e Has papers benchmarks distribution e Manual vs automatic reclamation e Region and alias annotated pointers within a coherent framework Scoped regions unifying theme alias open Polymorphism for code reuse2. Cyclone A Safe Dialect of C Michael Hicks University of Maryland College Park 1988 2005 In order to start copies of itself running on other machines the worm took advantage of a buffer overrun it is estimated that it infected and crippled 5 to 10 percent of the machines on the Internet More than 15 years later nearly half of CERT advisories involve buffer overruns format string attacks and similar low level attacks Low level but unsafe Must bypass the type system to do even simple things e g allocate and initialize an object Libraries put the onus on the programmer to do the right thing e g check return codes pass in large enough buffer For efficiency programmers stack allocate arrays of size K is K big enough does the array escape downwards Programmers assume objects can be safely recycled when they cannot and fail to recycle memory when they should It s not fail stop errors don t manifest themselves until well after they happen e g buffer overruns Credit where credit is due e Cyclone is a research language the product of many collaborators Greg Morrisett Yanling Wang Harvard Dan Grossman Washington Nikhil Swamy Maryland Trevor Jim AT amp T The C Programming Language e Critical software is often coded in C device drivers kernels file systems web servers email systems switches routers firewalls e most arguably beca
3. D W H ib iL ik he re U unique pointers R ref counted pointers L LIFO regions D dynamic arenas Bottom Line e CPU time 1 0 bound applications have comparable performance e All applications at most 60 slowdown GC has little impact on elapsed time e MediaNet is the exception e Memory usage Using GC requires far more memory than manual Cyclone manual techniques approach footprint of C original Throughput MediaNet Nn S z on of I e GC free O GC only 1000 10000 packet size bytes Experimental Measurements e Platform Dual 1 6 GHz AMD Athlon MP 2000 e 1 GB RAM e Switched Myrinet Linux 2 4 20 RedHat e Software C code gcc 3 2 2 Cyclone code cyclone 0 9 GC BDW conservative collector 6 204 malloc free Lea allocator 2 7 2 Throughput Webservers 4400 4200 sg e BoaC S D Boa Cyc Sed 3800 4 Boa Cyc unique Sen CycWeb amp EAI MA a a 1000 2000 3000 4000 document size bytes Memory Usage Web 635 KB reserved heap unique Boa Cyc GC Boa Cyc unique GC Memory Usage II Web reserved heap unique 282 KB 145 KB Boa Cyc unique GC 165 KB 146 KB Boa Cyc unique Memory Usage MediaNet MediaNet GC only heap refcnt other unique reserved MediaNet GC free Other Apps Cyc GC vs no GC Cyclone GC Time Mem 1 11 1 61 22 3
4. M 1 78 1 40 1 05 708K 1 80 4 00 1 0 192K 30 1 15 23 1 74 1 44M 5 19 Cyclone Manual Time Mem 1 11 1 61 12 5M 1 0 1 41 1 06 392K 0 99 4 00 1 0 8 2K 1 32 14 53 1 66 706K 2 49 333 0 99 31 8K 1 14 165 KB 146 KB Boa Cyc unique Memory Usage III Web CycWeb Other Apps C vs Cyc GC Test C Time Mem Epic KissFFT 1 33 394K Betaftpd 4 00 6 2K Cfrac 8 75 284K 8139too 334 27 7K 0 70 12 5M Cyclone GC Time 1 11 1 61 1 40 1 05 4 00 1 0 15 23 1 74 Mem 22 3M 1 78 708K 1 80 192K 30 1 1 44M 5 19 Things didn t talk about e Modern language features too Tagged unions and data types Pattern matching Exceptions Allocation with new e Porting tool e Lots of libraries Related Work making C safer Related Work Checking C e Compile to make dynamic checks possible e Model checking C code SLAM BLAST Safe C Austin et al RTC Yong Horwitz Leverages scalability of MC Purify Stackguard Electric Fence Key is automatic building and refining of model CCured Necula et al Assumes weak memory safety e performance via whole program analysis e Lint like tools Splint Metal PreFIX e less user burden Good at reducing false positives e less memory management single threaded Cannot ensure absence of bugs Metal particularly good for user defined checks e Control C Adve et al
5. easible in some environments So we must be explicit pt add pt Pp pt a p gt x q gt x p gt y q gt y return p pt a 1 2 void foo pt b 3 4 pe c add amp a amp b pt add amp b amp b c gt x 10 The types say it all pt add pt p pt q pt add pt P pt q pt add pt p pt q char zeroterm fgets char len zeroterm int len FILE Q Safe Manual Techniques Approach generalize regions track pointers New region kind Arenas Dynamic allocation but all objects freed at once And or impose aliasing restrictions Can free individual objects using malloc free or reference counting if aliasing is tracked When writing apps use GC first tune as necessary Can result in significantly improved memory footprint and throughput LIFO Arenas LIFO Arena Example e Dynamic allocation mechanism EPL well S a 5 A i P Image i e Lifetime of entire arena is scoped At conclusion of scope all data allocated in the arena is freed if tag infile lt x gt struct hnode r huff tree Like a stack frame but permits dynamic huff tree read_tree h infile allocation dynamically allocates with h e Useful when caller doesn t know how much i decode image infile huff_ tree memory needed by callee but controls F lifetime region r deallocated upon exit of scope else Unique Pointers Example e If obj
6. ect is known to have no aliases it can void foo be freed manually int x malloc sizeof int Pointer qualifier or U for short int U y x a E e An intraprocedural flow sensitive analysis x 5 ensures that a unique pointer is not used after it is consumed i e freed treats copies as destructive e one usable copy of a pointer to the same memory free y ey 7 Temporary Aliasing Alias Construct e Problem Non aliasing too restrictive extern void f int r x e Partial solution Allow temporary lexically scoped aliasing under acceptable conditions Makes tracked pointers easier to use Increases code reuse void foo int x malloc sizeof int alias lt r gt int f y free x With inference extern void f int x void foo int x malloc sizeof int x 3 f x alias inserted here automatica free x Interesting Combinations e Tracked pointers can be freed manually with free Or drop_refptr or automatically Pointers into the heap freed by GC Pointers into LIFO arenas freed at end of scope e Called a reap by Berger et al e Can use tracked pointers to keys to permit arenas to have non lexical lifetimes Lifetime of arena corresponds with the liveness of the key Called dynamic arena Ensuring Uniformity and Reuse e Many different idioms could be hard to use Duplicated library functions Hard to change applica
7. encing a pointer after the pointed to buffer has been freed Preventing Spatial Errors Thin Pointers e Don t allow dereferencing a pointer unless compiler can prove it s safe Often too conservative e Prevent dereferencing with dynamic checks May be able to eliminate some or all of these with static analysis or programmer provided type annotations Safety first then tune performance Thin Pointers Thin Pointers Thin Pointers Thin Pointers Types and qualifiers for more flexibility and or fewer checks char p char notnull pl illegal p1 NULL p1 p char notnull numelts 6 p2 illegal p2 p1 Thin Pointers Shorthand char p o oY aC oF fo oY CE KCS S eA Fat Pointers Fat Pointers Fat Pointers Fat Pointers Fat Pointers Fat Pointers Fat Pointers Shorthand ol eY 6 oe Be Pointer Qualifier Summary fat rep as a triple base upper curr supports all C pointer ops but any dereference may be checked notnull Obviates null check compiler must prove numelts n Obviate
8. ll live int r for short e Two basic kinds of regions A lexical block l e an activation record The heap H has a global lifetime Region Polymorphism void addTo pt P pt qa P gt x q gt x p gt y q gt y This is standard parametric polymorphism addTo V r1 V r2 pt rl x pt r2 void And this would be caught pt H add pt P pt a pt xr r x p gt x q gt x r y p gt y q gt y return amp r pt a 1 2 void foo pt b 3 4 pt c add amp a amp b pt d add amp b amp b c gt x 10 On the other hand pt H add pt P pt a p gt x q gt x P gt y q gt y return p pt a 1 2 void foo pt b 3 4 pt c add amp a amp b p d add amp b amp b c gt x 10 What has to be written is thus pt add pt p pt q p gt x q gt x Po gt y t g gt y return p pt a 1 2 void foo pt b 3 4 pt c add amp a amp b pe add amp b amp b c gt x 10 Dynamic Allocation e How can we be sure data is live e Can use a GC or safe manual techniques e GC based Data allocated in heap is given region H e Region is always live all dereferences are always safe Conservative collector reclaims dead objects Simple but little control over performance e Potentially significant memory overheads e Pause times May not be f
9. nux Cygwin OSX LEGO User s manual mailing lists Still a research vehicle What is a C buffer overflow include lt stdio gt int login char user 100 printf login scanf s amp user get password etc Calling scanf int login login retaddr char user 100 printf login scanf s amp user user ve 101st character int login rin retaddr char user 100 ADIN printf login scanf s amp user p gt s Abstraction violating Attack e Language and library abstractions may not be enforced Array accesses pointer dereferences type casts format strings trusted by the compiler e Other attacks exploit this fact Heap based buffer overruns Format string attacks User types login int login login retaddr char user 100 A DIN printf login scanf s amp user Stack smashed int login char user 100 printf login scanf s amp user p g Two kinds of Pointer Errors e Spatial Dereferencing outside of a legal memory buffer possibly at the wrong type Abstraction violating attacks in this category e Temporal Derefer
10. s bounds check compiler must prove Can refer to dynamic lengths zeroterm Pointer is zero terminated Fat Pointers Types and qualifiers char fat q Thin Pointer Dynamic Bounds P void foo int char for int i 0 i lt len i Daj S s Interfacing with libC FILE fopen char notnull zeroterm name char notnull zeroterm mode int putc char FILE notnull fgets char zeroterm numelts len int len FILE notnull Our buildlib tool easily generates platform dependent headers with signatures like these programmer helps Temporal Errors pt add pt p pt q pe r r gt x r gt y return void foo pt a 1 2 pt b 3 4 pt c add amp a amp b c gt x 10 typedef struct int x int y pt Simple Region Example pt a 1 2 void foo pt b 3 4 pt aptr amp a pt bptr tb addTo amp a amp b So this would go through pt H add pt Pp pt qa pt r malloc sizeof pt r gt x p gt x q gt x r gt y p gt y q gt y return r pt a 1 2 void foo pt b 3 4 pt c add amp a amp b pt d add amp b amp b c gt x 10 Preventing Temporal Errors e Tracks object lifetimes by associating a region with each pointer int A pointer can only be dereferenced while the region is sti
11. tion code e We have solved this problem by Using region types as a unifying theme Region and aliasing polymorphism e E g functions independent of arguments regions aliasing All regions can be treated as if lexical Temporarily under correct circumstances e Using alias and open for dynamic arenas Reference counted Pointers e Aliasing qualifier pointed to data have hidden count field e Aliasing tracked as with unique pointers Explicit aliasing freeing via a alias refptr a J void drop_refptr a Allocation Deallocation Aliasing objects what when objs static whole exit of ok dynamic region scope MEIENI single GC objects manual restricted Some Application Experience Boa web server Cfrac Prime factorization BetaFTPD ftp server Epic image compression Kiss FFT portable fourier transform MediaNet streaming overlay network Linux Drivers net video sound CycWeb web server CycScheme scheme interpreter Application Characteristics Program Non comment Lines of Code Manual Cyc Cyc manual mechs Boa 286 5 E 98 1 U Cfrac 183 5 E 784 25 UD Betaftpd 219 18 t 238 22 UR Epic 218 10 E 117 5 UL KissFFT 74 16 25 5 U 8139too 971 49 312 14 UD i810_audio 1500 57 318 10 RD pwe 55 1373 36 1024 26 RD MediaNet 8715 E 320 4 URLD CycWeb 667 U CycScheme 2523 UL
12. use it is low level Control over data structure representations Control over memory management Manifest cost good performance What about Java e Java provides safety in part via den data fields and run time checks tic memory management e Data representation and resource management are essential aspects of low level systems Some possible approaches e Compile C with extra information type fields size fields live pointer table treats C as a higher level language e Use static analysis very difficult not perfect less modular e Ban unsafe features there are many you need them Outline e Status e How Cyclone handles pointer errors Spatial Errors Temporal Errors e Programming Experience e Performance Analysis Projects using Cyclone Open Kernel Environment Bos Samwel OPENARCH 02 MediaNet Hicks et al OPENARCH 03 RBClick Patel Lepreau OPENARCH 03 STP Patel et al SOSP 03 FPGA synthesis Teifel Manohar ISACS 04 O S class at Maryland 2004 2005 Cyclone Safe memory safety abstract types fail stop C level user controlled data representation and resource management easy interoperability manifest cost Convenient may need more type annotations but work hard to avoid it Modern add features to capture common idioms Status gt 110K lines of Cyclone code 80K compiler libraries 30K various servers applications device drivers gcc back end Li
Download Pdf Manuals
Related Search