ATFundament of High Perf Comp
ATFundament of High Perf Comp CS 6463
Popular in Course
Popular in ComputerScienence
verified elite notetaker
This 209 page Class Notes was uploaded by Mireya Heidenreich on Thursday October 29, 2015. The Class Notes belongs to CS 6463 at University of Texas at San Antonio taught by Staff in Fall. Since its upload, it has received 42 views. For similar materials see /class/231388/cs-6463-university-of-texas-at-san-antonio in ComputerScienence at University of Texas at San Antonio.
Reviews for ATFundament of High Perf Comp
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 10/29/15
ust Management S 6463 Lecture 12 Prof William Winsborough February 27 2006 Business I Next paper lil N Li J Mitchell and W Winsborough Design of a rolebased trust management framework IEEE Symposium on Security and Privacy 2002 Preliminary synopsis due March 6 I Reminders ll Preliminary project proposal Due Wednesday March 8 ll Extended synopsis for Distributed Credential Chain Discovery due March 8 February 27 2006 Winsborough CS 6463 Lecture 12 v 1 Discuss Forward and Backward Search Algorithms I Refer to specification in JCS paper February 27 2006 Winsborough CS 6463 Lecture 12 Storage Type System I Each role has two types a Issuerside type Issuertracesnone Issuertracesdef Issuertracesall w Subjectside type Subjecttracesnone Subjecttracesall February 27 2006 Winsborough CS 6463 Lecture 12 Welltyped I Welltyped role names JDef5p27 I Welltyped role expressions JDef6p27 I Welltyped credentials JDef7p28 February 27 2006 Winsborough CS 6463 Lecture 12 Access Control and Trust Negotiation CS 6463 Lecture 6 Prof V lliam V nsborough February 7 2007 Harrison Ruzzo and Ullman 1976 I We continue studying this classical paper in access control Mum 2m7 Winsbamuvh csam udure 39I Undecidability in the General Case I Reduction of any Turing machine to a protection system that enters rinto a cell if and only ifthe Turing machine halts Mum 2m7 Winsbamuvh csam udure s Business I I will soon post a collection of papers that you can consider presenting in class 3When you find a paper you would be interested in giving a try send me a note ianCh paperwill be allocated to the person that first requests it Some papers no one selects I will present Mum 2mm Winsbmauvhcs m lama 2 I Decision Procedure for all Mono operational Systems I When the commands are parameters to the decision procedure the problem of deciding whether a protection system is safe is co NP complete I Reduce k clique to safety I Question why doesn t this result contradict the result that for a given protection system a polynomial algorithm can be found Mum 2mm Winsbmauvhcs m udure A 39I Recall What a Turing Machine Is I Each Turing machine T consists of i A nite set of states K an IL A distinct nite set of tape symbols P P includes the nanksymbo B I B initially appears on each cell of an infinite tape ill Tape cells are numbered 12 L I There is a tape head which is always scanning located at some cell of the ta e I Moves are specified by Mum 2mm Winsbmauvhcs m udure Turing Machine Computation Moves m are specified by a mncticin c m F a m Fgtlt Li R mm x p v Rfurstates p and u and tape symbols x and vi then snciuic theTuring machine Ttind itself in state u With itstape head scanning a ccii n lding symbol mnch Enters state p erasesX and printsY an the tape ccii scanned and mDVES itstape head cinc ccii tEI the i t it m x p Y Litnc Same thing happens butthe tape head mDVES cinc ccii ieftbutneveruffthe left cn thhetape atceii i Fahilal m Wimwgi csstm cm 6 Termination is Undecidable l Initially T is in state 75 the initial state with its head at cell 1 l Each tape cell holds the blank I There is a particular state qv known as the nal ta 5 e I It is known to be undecidable whether started as abov a a an rbitr ry Turing machine Twill eventually enter state q mm m Wiuwcicscmimc Theorem 2 I It is undecidable whether a give con guration ofa given protection system is safe for a given generic r39 Reducing Turing Machine Termination to the Safety Problem m 1 aluminum vi i r l 5 IX V y L39 lllr1itt l ma mm lightlhcn w mm o M ii ma ai tic a um tie quota ngm new is wian Human mm rm m m inn m Fahnal m Wiuwcicscmimc tame 0l1i139l ll n in I ll land a in u l am A u n at n m pi it lac x m o 1 mm mm r RoleBased Access Control RBAC I Rules introduce a level ullndllectlun between users and permissons i remmssuam up blems ii We mop We an aggregating mes see new aegieeaep 5m eels and nng on those a me aths mm 5 more mm A u no oil Users Roles Permls ons Wm n 11 ml 1 Aime les Signchecks memo l 1 ea Bap me Wrasse alder buyer Z iiie employee CBW e crllarlager mm m Winemgieseeome a mm m Winemgieseeime o u i Goals and Features Issues I Facilitate security administration and I Level at which implemented review 0 Typically done at the application or iii Centralized administration middleware level iil De ne security policy in terms of i Little support exists at 08 level rganizationa r les I poncy ne quot I Relationships can exist between roles iConsistent with both ii Mutual exclusion Mandatury Access Control MAC ii Role inheritance isoretionaiy Access Control DAC renew m Wimmieseteeme u mm m Wiuemgieseteime is Supported Security Principles i re system glvlrlg eaon role unly permissions reuulre to perform assuclated tasks I Data abstraction i Depends on implementation detalls application or rnlddlevvare mum m Wllxmmlglcsskmuwms n Four Reference Models RBAc3 RBACl RBAc2 RBACU mm m Wiumigiessteims ust Management S 6463 Lecture 10 Prof William Winsborough February 20 2006 Business I Preliminary project proposal LiDue Wednesday March 8 I Advertisement WI have funding for PhD students working in trust management or information flow February 20 2006 Winsborough CS 6463 Lecture 10 252 77 Example Expressivity in Credentials I Deferring a Guaranteed Student Loan BankWondeferGSL lt FABaccreditedfutimeStudent FABaccredited lt StateU 7 StateUfutimeStudent lt URegistrarfutimeLoad StateUfutimeStudent lt URegistrarparttimeLoad m StateUgradOfficerpthandidate at URegistrarparttimeLoad lt Bob 7 StateUgradOfficer lt Carol 7 Carolpthandidate lt Bob February 20 2006 Winsborough CS 6463 Lecture 10 3 RTO Syntax I Basic structure is a role ie an attribute Ar A is a principal authority for Ar r is a role name I Four types of policy statement i i Ar lt D Role Ar contains principal D as a member or Ar lt Br1 Ar contains role Br1 as a subset Ar lt Ar1r2 Ar contains Br2 as a subset for each B in Ar1 ii Ar lt A1r1n A2r2 Ar contains the intersection I A credential is a statement signed by A the credential issuer and the authority over Ar I The first 3 statement types give a language equivalent to pure SDSI February 20 2006 Winsborough CS 6463 Lecture 10 Setbased Semantics for RTO l Given as set of credentials C the semantics of C is 5C Role gt Entity given by the least function rmem Role gt Entity that satisfies the following system of set inequalities rmemAr 2 exprrmeme Ar lt e e C I Where i exprrmemB B L exprrmemAr rmemAr l7 exprrmemAr1r2 U rmemBr2 B E rmemArl l exprrmemf nf n n f n exprrmemf 1 2 k 1ltjltk February 20 2006 Winsborough CS 6463 Lecture 10 Calculating 5C February 20 2006 Let SF Role gt Entity F SF is the function type that is the space of all semantic functions Let LIJC SF gt SF be given by LIJCrmem Ar U exprrmeme AR lt e E C LIJC is monotonic and SF is a complete lattice lquot Tarski 1955 The least fixpoint of WC exists Note that the least solution to the set of set containments on the previous slide is identical to the least fixpoint of LIJC The least fixpoint can be calculated by taking the limit of LIJC39 SF where LIJC0 Ar g and LIJCi Ar U exprLlJCie AR lt e E C Winsborough CS 6463 Lecture 10 6 Credential Chain Discovery I Outline l Sound and complete evaluation model Based on graphical model credential graph 7 l Efficient search for proof of authorization l Provides a basis for discovering chains when credentials are stored in a distributed manner Evaluation steps can be interleaved with credential retrieval steps February 20 2006 Winsborough CS 6463 Lecture 10 Algorithmic Contributions I Search algorithms l Worst case efficiency as good as any existing algorithm Backward ON3 time N number of credentials Fonvard ON2M time M sum of credential sizes Both directions ON2M time l Well suited to the application Efficient when there are lots of unrelated credentials Changes to credential pool do not degrade performance Graph search can drive credential discovery February 20 2006 Winsborough CS 6463 Lecture 10 7 Example Student ACM Discount I EPubstudentACM lt EOrgstudent m ACMmember I EOrgstudent lt EOrguniversitystudent I EOrguniversity lt FABaccredited Credential Discovered in Backward Direction I FABaccredited lt StateU I StateUstudent lt URegistrarparttimeLoad I URegistrarparttimeLoad lt Alice Credential Discovered I ACMmember Allce in ForwardDireclion February 20 2006 Winsborough CS 6463 Lecture 10 U Credential Graph EPub gives a double subscription discount Type 1 FABaccredited StateU Type 2 EOrguniversity FABaccredited Type 3 EOrgstudent EOrguniversitystudent Type 4 EPubstudentacm EOrgstudent n ACMmember EOrg student Key TCredential ISummary February 20 2006 EOrguniversity EOrguniversitystudent FAB accredited i StateU StateUstudent URegistrarparttimeLoad Winsborough CS 6463 Lecture 10 EPubstudentacm EOrgstudent n ACMmember At ACMmember Alice Littear Proaraww39 Q Haw olam wksea og EXQMPLL A con rmt7 Produces U S W44 CL Q V9 Mpro f eor o CL GCV 55 2 de av a k le Macuhe Group 4 laced t wAr hp d de 0L 6514 M4 4 n 39 H r 40146 Machiw 6quot 13 Mad 2 L er 19 Wow cc 0 Chan 44 6 Llok n n u Rx elm HACK m 419N 20 Norma can gar area 14 W4 OU quot I a 39l Haw MAMY aka M 404465 3519144 we Lek10 ensqu per day can cater u magma 61 mg Vartagles Ce quot 05mins Produce ah maable antVa F CG a quot h quot quot 3 4 1 H 39r 1 I 9 8 h n a h r 3 Couswu39K 464 a in slzo Z Cgf 6tg 72 doSeva chh oh WWW Max w ie 239 Ca CR it in wee a emuvi Vavtaslqi x4X k Lakshmmr k4 at x a x4 5 La La auxnu r 24 x4 gs Inn anquot X413quot Qh4 q E Eh 0960 LIA90939 Maxtmee 364 ax chg Cd X4 H Mar MM39M an 0 MAC 4 H Mg o EndI coosmi k is a haw spam 34 24 a Set o quot 3 in 2 Saulng ha aquot Comb3 quot1m 9356 at aF m Wequot WW 074 9 MAXCWEhg ZC4Cd l 2 Lusaka A gataIL 44 s evactse it 4quot ch c i Lx x4 0 HM t o uivS E l c akn dvcg 0 We a egg E ISA ERR Ftshnoto 920 00 IuArfrwtzxfxw eh psh wrtnm r 9325me 932 2 PR novaTia 5 E 9 hi on 9 19min Covcm w 7 upth xmym 9 y 82 giganfatfn boxltnx 113 pr an rorrmi aw 9 53 5 zoom Slrkmaoto Pst mtspbtor F r as mSSmnPto 914 loanntor Anaernq9o Ad 9 934 Di lt dl 3 Cew uev 0oon i6 u UHIsa Hngpbu gs an 4 Set H cq39 a tau Manes in IE2 mw Th Comex puma Nam C n L MM 4 Lg IHI4 35 2 C in 6H 3 slit Sth H Mo 9 1 4 a 03 32 this M 37 ll C4 IhkTS tHal p aucg H s Caz lanlwgd 149th we 6 C quotMadCgavtx at on ca 0 A54 Omenml 91 We flamr Sakaiv stous 0 lWRJ39SlCquot CDHVCX Rania in DQUMR u 4 m u lamale w e93 WLMOQJ Hahn3 H CWI39CrSecHoH grind3 vcw us CH CanCz In 3 Ton OL 4 OOH03 Q TL Z gt4 TL 004 32 raunc kj loe 0 We 0U0 Inaf UHS I Coll Cg avg Wyequot N W Plowhe sweep heatclap cm 00quot upth 0 IerSccf39 Camx 3605 A Th Yam 0 rut4 an cr InnaSect Halif ahe f Tm 0W 1quot 00 23116 gt 4 TL me look Lake sweep or InhrSed Caavex 216mg 7 k3 39 Shvc why Yaokai HaIOH C Sarkol L s 44 a ag c of a hkt el u4 RPMQMH S 141 24 lh aL 39 Lowqu of C fay 155 PM ha M I L 393 o Swap from 09 0 Bellow wacu39h adv 124349 vCQMC4 at 9 41 Ca ream ca 1 J Cukfsec39Ia l4 sweep Cu 2 454144 Wightz 0 Take vw us o C1 C 0 enw poSwH Me Eve Wad 19 anew 10 e 4 an ee BowMara 04 C4 o h 2 a Lglfpttk dt Ha U e hit e amCZ 4 clay o a aid 91er 0 lGe iC and Lul luat 0 60114 C I an ca e 397 La Cz O 7 W 27 a f cz amp Rout umrquot M1490 4 mm Qcovx md 44quot even WG3 gt OLh Hunt aimedQa 17 equqaurl13193n JO p174 lt1 3quotquot3n h 33 quot 1 19quotquot l 37 v2 V7 KP quotwait 91 lt 3quot 1 2133 h lt 7 E 6276V3 ltV 2 f T New 3136th 4 0 X71470 MaJo Lynn 11 Haw WU quot397 3 39 3 70quot UVWj 3n 39v1H 43mm 07 fi39 quot 7quot quotIquot quot399 W V 3 PVU J h7 l quot9 n7n0a o I gaffquot 93 932 7w 3 AWcWJuLmvo 33 2T 4 91 3 9032705 awb mn v 339 W Vrl 3 quot 339 39 slur wow WV mmaw new 5 a 7 7 Mme o W W 39 H Y 23H quot3quot 6 7 YMPW MWDMJ Wnn vwogsvaavnm onl fugwmwvmd 19 37 Omvn anqwl Hawaii We Lit Vc w Lef Et l I Xl fz x 2 b0 i h 4 www l l quot 6 k2 3 UA39 1 Mad 40 ded 4 d ueu oml L P 6 me fat 94th x aunt mug and 1 Mm 5 6M4 9 h Lay X5 k I beg 0 tab s Canada 49 Vac riin gt Wide redWk is C Qa t I Xaam 4 2 1 M tee Guiyang 20 s smawa at X akflh a a a Ant 3 swam 40 49 3964 e L gt M xug gtxn39au 14 LPLc in euiuc 0kewkc war x045 or xaam I 44 09 M defme 9 5 N 35 quotwk W Wk anew aflv39wm1 verkx Vi 0r decide 4440 W LP is 39wfmsihk a 0039 Hum 4930er 21gt 30 LP H 239 Ade H inndimensional LP 21 wm 2qu L U432 f3 imwisle OHaerHLSe vaport 146 WcoquUmllu Sh39l 39a faintI M mantles fax A Let Mm L a 4m Ln pa n a H 2 Let vz a a Coma of c vzums mue assume 3 amp g to y d2 4L LPIW u via 6 quot 5 v v 6 g V Paidquot 0390 L 1rf Wimim 2 9 S J 0 Ie ka a He 2 Such 0 foiwr do quotof egg tit 7 Mort vd39 Hm LP 4 cakewalk 0 aka ll HAWM v nalists R39AM H39MC EOLZ OLPIZ i1 S l39OTAo 0 VI 1M Ekau fa which Mn 03 44quot in every Skf z QMQUA teal mamaIa Linear Proamuamiai a Mame order of Plahej My What gt rm u SchJun 00 44 out 1 39Dts nah WNW agortw h gorIHAM 23 Zaudomxeed KMMLP Hi 4 Compwle A WOW thfm a oa Luv7 quot o 39Hne 51Plam i H 7 Quita Baddh ru wh onLHBM 2 29 MduL9 Uh assume 4 exfskhce q l q madam MU A er 31her Wm Uc atherwk a 39M39M t39ukoer Colwee A at khan k in Cot ck PM Qh0iw Mac MinHob a lupul I Gun army A 394 v3 MIMI T14 my A QS HA Le same demonIs N d in A rahoh order dag kh dowwl39o 2 i 3 W Chdu z Rahdauq k 3 SW A Dr will a LThdt39hk Access Control and Trust Negotiation CS 6463 Lecture 4 Prof V lliam V nsborough January 31 2007 Harrison Ruzzo and Ullman 1976 I An abstract model of protection is presented I A notion of safety is introduced I It is shown that am general it is undecidable whether a specific right will be added to the system I JIn restricted cases the problem is decidable MW 2mm winmmuv c5545 WW4 The Paper Does not Present an Analog of LRk I Monooperational systems are not terribly realistic MW 2mm winmmuv c5545 WW4 s Business I We will discuss HRU76 for two periods I I will post the next readings for Wednesday 27 by the end of the week I I will also post lecture notes JinnahCM 2mm winsmumsam WW4 2 I Comparison with Ambiguity of CFGs I A contextfree grammar is ambiguous if there are two parse trees for the same sentence in the language I Deciding whether a contextfree grammar is ambiguous is undecidable in general I All LRk grammars are unambiguous and it can be decided efficiently whether a grammar is I Most interesting programming languages have grammars MW 2mm winsmmcsam WW4 4 39I Definition Protection System I Referto section 3 of HRU76 MW 2mm winsmmcsam WW4 Model Checking and Code Generation for UML State Machines and Collaborations By Knapp and Merz VVVVVV Ovavmw Introduction Relevant UML Notations HUGO Code Generation Model Checking Conclusion Introduction gt Unified modeling Language is defacto standard for designing and architecting software systems gt UML offers various diagram types gt UML model consist of set of diagrams that together describes the single system gt It provides diagrams for the static dynamic and architectural aspects of systems UML Diagram Classification gt Static Use case diagram Class diagram gt Dynamic State diagram Activity diagram Object diagram Sequence diagram Collaboration diagram gt Implementation Component diagram Deployment diagram C 9 Relevant UML Notations gt Class diagram lays out the static structure of the system gt Classes define attributes operations and signals 0 2i UML Notations gt Dynamic behavior is specified by state machines for the classes ATM and Bank gt States can be simple composite and concurrent composite state contains orthogonal regions siaie Manhin mi a State machine diagram for Class ATM gt Example state machine simulates the interaction of an ATM with a user and bank computer gt Simulation focuses on card and pin validation 532 Mam warm 4 s C State Machine Diagram for Class Bank gt The bank computer validates the bank card concurrently to the pin code Transitions gt Transitions between states are triggered by events gt Transitions may also be guarded by conditions specify actions Events to be emitted when transition is fired gt Transitions without an explicit trigger is called completed transitions gt Events may also be emitted by an entry and exit actions gt Actions are executed when the states are activated or deactivated Collaboration Diagrams 3 Expected Collaboration gt Expected interaction between an ATM a and a bank lterilllilllll aim titlii lPlllO IiiquotSlant AquotPlNVeriie tlgI f lzl39eenlgrElll Collaboration Diagrams gt Erroneous collaboration describes an undesired behaviour 1zleriilielilo azlggrlPllio iai lanl ss39rl39 Pirileringl 4 2 ahml HUGO 7 Tentativer called set of tools gt Model checking technology is used to ensure to relate UML state machines and interaction diagrams HUGO supports the generation of java code 7 gtgt Propose to generate code in detail from the UML model Formal analysis and code generation are applied to the same model anaIySIs Why code generation gt UML encourages the redundant descriptions of the same aspects of a system gt Redundancy generates an obvious opportunity for verification and validation techniques gt Details are abstracted away when finite state machine built for verification V When implementing the state machines information needs to be put back to the code One Possible way to generate state machines 2 A state machine is generated as a set of variables gt State is generated as a closed set of combinations V An event is generated as a call to a member method gt A guard generated to an If statement A transition is generated as an assignment gt An action is generated as function call Code generation in HUGO gtgt Hugo produces Java code gt Standard runtime component state for UML state machines Every state of a state machine is represented by a separate object gt Objects representing the event queue and event dispatcher are generated for every state machine Code generation in HUGO gt Event Queue two queues one for completion events and one for ordinary events Active concurrent composite state contains one active sub state and the contents of event queue Containing events received but not at dispatched gt Event Dispatcher Hands the event to the top state of the state machine Dequeues the first event from the queue Code generation in HUGO gt Transition Selection Implemented by greedy algorithm Event traverses the state hierarchy until one or two states are found that consumes the event lnnermost transitions are prioritized as required by the UML model Code Generation in HUGO gt Hugo generates gt Java class Contains method bodies for the specified operations and signal receptions run method Auxiliary classes For all declared events For all guards and actions Code Generation in HUGO V Hugo code generation V Interpretative in nature gt Represent UML semantics as faithfully as possible V Not intended to produce product quality and optimized code gt Code generator supports all features of the UML state machines except for time and change events Model Checking Component Of HUGO gt To verify the consistency of state machines against specification expressed by collaboration or sequence diagrams More sophisticated verification is possible Hugo backend for model checking compiled UML state machines into Promela It is an input language of the spin model checker Model Checking gt SPIN backend of HUGO 2 Instead of objects processes are generated for each state The transition selection algorithm depends on passing messages between these processes V7 1 Successful run produces counter example Model Checking gt Hugo implementation made use of symmentry arguments to reduce the amount of nondeterminism gt Relied on the compression algorithm implememted in SPIN to reduce the memory requirements gt ATM example taking spin about a minute to analyze gt Optimized translation such that generic processes of the original translation are replaced by processes tailored to the given model gt ATM example can be analyzed in a second gt Except deep history states sync states internal transitions time and change events Model Checking gt Third component of Hugo is backend for the real time model checker UPPAL gt Required different compilation strategy gt They had taken several design decisions because UML model does not support a particular timing model gt The UPPAL backend is the least component of the Hugo component Access Control and Trust Negotiation CS 6463 Lecture 5 Prof V lliam V nsborough February 5 2007 Harrison Ruzzo and Ullman 1976 I We continue studying this classical paper in access control mama 2m7 wlnsmlv csaala lama l 39I Safety I Def A command leaks generic right rfrom configuration Q if IIJThe conditions are satisfied and lKOne of the operations puts r in a cell that didn t previously contain it I Def Initial configuration Q0 is unsafe for r if there is a configuration Q reachable from Q0 and a command that leaks rfrom Q mama 2m7 wlnsmlv csaala lama s Business I Projects can be done in teams mama 2mm wlnsamwacsam lama 2 Example 4 Unix I Privileges are granted to owner and to everyone e se ilApparently group privileges were added later I User u owns file f if own in u f I Files are encoded as subjects ijUseru can read le fif own in uf and owner can read in fquot or anyone can read in ffquot mama 2mm wlnsalmlvacsam lama A 39I Safety in Practice I If you re trying to decide whether you should grant a right you may want to remove yourself the owner from the initial configuration before asking whether the configuration is safe mama 2mm wlnsalmlvacsam lama tromhe Sweet 0 Wracf ampe V3 9091M W mum ihkrdeds m a v1 new Merck Sim V3 05M 2 dew ca k 4w b M Lin Mp a sigh x 4 m4 pow 1e 12 5 am m 1mm 6M 3911 rquot If f o 44quotquot is CI 8 P G S Jlt 139 ep 2 mum we I I If 3 dug sik of q la on I O MW itf rziwa qullq are clear a a 33 we 2 awaken cf quotacetic or v47 Wrb m it 0 ct c V1 W out V1 01 Sheep Una NM Flak 5e Fain xy Sf daisK 127 p did 234 v 90 an Excel xik p fkn v I 4 IT I l 39 LPxxf l 1393 71 3192 t e 39 92Muueg zmy 23 456 x39 sf z 461 4 y 9x 7 L LJWM if 539 IO Sik weds Sweep the 4 w you squot c by Pan ob in 6 MN are a CA M 6 o quota 395 v1 shirt in 6 4mm ou m SK W an 39 8 nd u W arc g awe ah 444 Law Chet Hannah a SNc Evehf 00 0 958041 exn S Hu Pawns 87 r 3 f 90h yaw 3 39 15 Wm or wk Av V quot iz x x 4 F 7 ay1v 5 a f 9 7 V v v 39 P37 51v M pl 12gt uponme and 3 N am e P 7 0kg Inkracgk P39s Iv Jadea 33 w 0 50 ma wf WWW quot F g 7 0 ch C PM ML Pc J Pi Po G hi Woe 0 I gnauc mllysmlt 0 394 a 3amp9 f or g M N 4C 39 I i 0rd amH on u39 s wiukvb fwd1 a on oc39 wanna 6 39Mxhct xlus nq o Cain c C M KVO H fu 95 pk ARI when e fn k gun J M9 sik in iukn or o C MW WIquot 3 Ulku t Cwh1 up 10 3 Me M1 m h Lg wukc q 3 VI verkx 4w sq 4 V3 aw 6 9 Th4 The 7 way it Much 0H r em mqprqr m a Guilike SW 4 Q39V Q 0quot b 38 ml y 53 23 us 858 3 33 its 33 ii 30 386 9 pr Plu 30583 033 3amp9 3303 w J 356 a 33 key 65 23 738 u v3 0 90 3238 3amp4 3 30V 121 04 32 8amp 3 3 by Va 100 9 harmony 05 I39ll 3 58 7 u 39540 0 9quot 057 o i 3 quot650 3840 I 1 26 65 um I a E E E is 13 2313 s v towsw G 75 ii 0 VJ J03 xix it x430 056 30 5 056 H 1 D398 1 393 To 448 0 8 05 VJ 1W n 8i 8 13 323 1 u 416 93 003 33 490 t4 of vxoos l 430 3 95 58345 3 39ll l l 9353 166 Algorithm VORONOIDIAGRA MtPt Input A set P 2 pl i 7 of point sites in the plane Output The Voronoi diagram Voi39Pl given inside a bounding box in u doubh 1 ofJIJAUJIJ connected edge list D Initialize the event queue Q with all site events initialize an empt 5mm structure quotI and an empty doublyconnected edge list 39D while Qis not empty d0 Remove the event with largest coordinate from Q if the event is a site event occurring at site 7 then HANDLESITEEVENTp else HANDLECIRCLEEVENTW where yis the leaf of 239 repre senting the are that will disappear The internal nodes still present in 2 correspond to the half in nite edges of the Voronoi diagram Compute a bounding box that contains all Ver tices of the Voronoi diagram in its interior and attach the halfin rme edges to the bounding box by updating the doubly Connected edge list appropriately Traverse the half edges of the doubly connected edge list to add the cell records and the pointers to and from them Davcuties 10 ks Kc ycoout 6 M it 067 W I4 44a 3 39 gr 051 Seer mamasr cng curedz MGMquot 0dr alaMilM WM Swen mom 393 79quot m Sake iotaRoi r 114mg nkM39s sweep rm L39s 790 lava Qua 0M OL I Span H Y39DLESITEE39ENTI l 39Ji 1f 2 is empty insert p into it so that T consistsof a single leaf storing pg and return Otherwise continue with steps 273 V Search in 239 for the are U vertically above 7 It the leaf representing a has a pointer to a circle event in Q then this circle event is a false alarm and it must be deleted from Q 39 Replace the leaf of 39239 that represents at with a subtree having three leave The middle leaf stores the new site pi and the other two leaves store the site 7 that was originally stored with at Store the tuples pp2 and pp representing the new breakpoints at the two new internal nodet Perform rebalancing operations on T if DECessary Create new half edge records in the Voronoi diagram structure tor the edge separating 1quotp and l tpl which will be traced out by the ttw new breakpoints I V Check the triple of consecutive arcs where the new are for p tsthe left are to see if the breakpoints converge If so insert the circle event into Q and add pointers between the node in 39T and the node in Q Do the same tor the triple where the new arc is the right arc Jleu s uk colM Le up Nah any 4 g MFR mute Art A 119 8n u pi fun 50A pm 343 owns Hm pa even d h CVCh H39 HANDLECIRCLEEYENTWJ l 7 Delete the leaf y that represents the disappearing arc 0t from 392 Updale the tuples representing the breakpoints at the internal nodes Perform re balancing operations on 239 if necessary Deleteallcirgle eL39ents lgVOh ing g flog these can be found using the pointers from the predecessor and the successor of y in CT The circle event where 0t is the middle arc is currently being handled and has already been deleted from Q Add the center of the circle causing the event as a vertex record to the doublyconnected edge list 17 storing the Voronoi diagram under con struction Create two hali39vedge records corresponding to the new break point of the beach line Set the pointers between them appropriately At tach the three new records to the halfedge records that end at the vertex Check the new triple of consecutive arcs that has the former left neighbor ofa as its middle are to see ifthe two breakpoints ofthe triple converge If so insert the corresponding circle event into Q and set pointers between the new circle event in Q and the corresponding leaf of T Do the same for the triple where the former right neighbor is the middle arc oiledn Kw per evewl Eat twisted cued outta um wax 01 law t alarms are mu M Ma are l w Poihdj 5 null 30quot ch ul ive in u pkhc cad u M ptM39MM 057 Mkm or Slog a inkSalim HM 7 JQ JJ IDuMHz kw Os Qh on mp3 a A Jef 0 fun o 3 of the such Mod rink Mam are pmevved u emu u Moms acme7 MM Pn39hxl Duns WW 9fquot1397 like P Y X j Line 3 hX Bid 39M 395 if V PI 0 P x a P p zquot 2 Lu 9 l a 6 fquot wadon Emmy GEE Puts Law 1 4 1 Lin abut 9 on gKW y Gav 3 I Goa fewNa it y MR 3 e Esra6N he 9 7 w naht ya 5 l 33 em in 9 Fh vij r1a9 31 a Vernal dislm 4 oul 1quot II 11 quot quotHI ust Management S 6463 Lecture 9 Prof William Winsborough February 15 2006 Business I Next week we will continue discussing the paper posted for today N Li W Winsborough and J C Mitchell Distributed Credential Chain Discovery in Trust Management Journal of Computer Security 1113586 February 2003 I Syropsis due 220 should discuss pages 1936 sections 47 lquot Focuses on finding credential chains when credential storage is distributed I Only one extended synopsis will be due for this paper lquot Due March 1 l Make it a really good extended synopsis February 15 2006 Winsborough CS 6463 Lecture 9 2 Today s Lecture I Guest lecture I AudiT and Trustbased Access Control ATTACK 1 Sandro Etalle Associate Professor University of Twente Distributed and Embedded Systems Group I Yourjob ij 1 Critique i 1i Ask tough questions February 15 2006 Winsborough CS 6463 Lecture 9 252 77 Example Expressivity in Credentials I Deferring a Guaranteed Student Loan BankWondeferGSL lt FABaccreditedfutimeStudent FABaccredited lt StateU 7 StateUfutimeStudent lt URegistrarfutimeLoad StateUfutimeStudent lt URegistrarparttimeLoad m StateUgradOfficerpthandidate at URegistrarparttimeLoad lt Bob 7 StateUgradOfficer lt Carol 7 Carolpthandidate lt Bob February 15 2006 Winsborough CS 6463 Lecture 9 4 RTO Syntax I Basic structure is a role ie an attribute Ar A is a principal authority for Ar r is a role name I Four types of policy statement i i Ar lt D Role Ar contains principal D as a member or Ar lt Br1 Ar contains role Br1 as a subset Ar lt Ar1r2 Ar contains Br2 as a subset for each B in Ar1 ii Ar lt A1r1n A2r2 Ar contains the intersection I A credential is a statement signed by A the credential issuer and the authority over Ar I The first 3 statement types give a language equivalent to pure SDSI February 15 2006 Winsborough CS 6463 Lecture 9 Setbased Semantics for RTO l Given as set of credentials C the semantics of C is 5C Role gt Entity given by the least function rmem Role gt Entity that satisfies the following system of set inequalities rmemAr 2 exprrmeme Ar lt e e C I Where i exprrmemB B L exprrmemAr rmemAr l7 exprrmemAr1r2 U rmemBr2 B E rmemArl l exprrmemf nf n n f n exprrmemf 1 2 k 1ltjltk February 15 2006 Winsborough CS 6463 Lecture 9 Calculating 5C February 15 2006 Let SF Role gt Entity F SF is the function type that is the space of all semantic functions Let LIJC SF gt SF be given by LIJCrmem Ar U exprrmeme AR lt e E C LIJC is monotonic and SF is a complete lattice lquot Tarski 1955 The least fixpoint of WC exists Note that the least solution to the set of set containments on the previous slide is identical to the least fixpoint of LIJC The least fixpoint can be calculated by taking the limit of LIJC39 SF where LIJC0 Ar g and LIJCi Ar U exprLlJCie AR lt e E C Winsborough CS 6463 Lecture 9 7 Credential Chain Discovery I Outline l Sound and complete evaluation model Based on graphical model credential graph 7 l Efficient search for proof of authorization l Provides a basis for discovering chains when credentials are stored in a distributed manner Evaluation steps can be interleaved with credential retrieval steps February 15 2006 Winsborough CS 6463 Lecture 9 Algorithmic Contributions I Search algorithms l Worst case efficiency as good as any existing algorithm Backward ON3 time N number of credentials Fonvard ON2M time M sum of credential sizes Both directions ON2M time l Well suited to the application Efficient when there are lots of unrelated credentials Changes to credential pool do not degrade performance Graph search can drive credential discovery February 15 2006 Winsborough CS 6463 Lecture 9 Example Student ACM Discount I EPubstudentACM lt EOrgstudent m ACMmember I EOrgstudent lt EOrguniversitystudent Credential Discovered in Backward Direction I EOrguniversity lt FABaccredited FABaccredited lt StateU StateUstudent lt URegistrarparttimeLoad URegistrarparttimeLoad lt Alice Credential Discovered in Forward Direction ACMmember lt Alice February 15 2006 Winsborough CS 6463 Lecture 9 U Credential Graph EPub gives a double subscription discount Type 1 FABaccredited StateU Type 2 EOrguniversity FABaccredited Type 3 EOrgstudent EOrguniversitystudent Type 4 EPubstudentacm EOrgstudent n ACMmember EOrg student Key TCredential ISummary February 15 2006 EOrguniversity EOrguniversitystudent FAB accredited i StateU StateUstudent URegistrarparttimeLoad Winsborough CS 6463 Lecture 9 EPubstudentacm EOrgstudent n ACMmember At ACMmember Alice Principles of Program Analysis An overview of approaches cccc 63 The Nature of static analysis approximation Static program analysis predict the dynamic behavior of programs without running them I Example at each program execution step what is the value of each variable int x y z readampx if xgt0 yx z 1 elseyxz2 I The question cannot be answered precisely bc the program input is unknown 1 We don t know the value of x and therefore cannot predict which branch will be taken whether the value of x is greater than 0 1 However we can predict all the possible values for z and that y is gt2 0 at the end of code I Program analysis approach tries to give approximate answers tries to prove properties of program entities variables functions types c56463 2 The Nature of Approximation may and must analysis n Since the behavior of programs cannot be predicted precisely there are two ways to approximate I Over approximation what may happen when all possible inputs are considered a The answer is a superset of what happens at runtime I Under approximation what must always happen in spite of different inputs in The answer is a subset of what happens at runtime I What approximation to use depends on what the results will be used for I Should always err on the safe side in Example if we want to remove all useless evaluations in the program should we find evaluations that may or must be useless in The relation between may and must analysis I Find all evaluations that are always useless must analysis ltgt find all evaluations that may be useful may analysis c56463 3 The Precision of Approximation How input sensitive is the analysis El Flow sensitivity Is solution sensitive to the control flow within a function I Flowinsensitive analysis D Example what variables may be accessed by a code a Solution find all the variables that appear in the code I Flow sensitive analysis 1 Example what values a variable may have at each program point 1 A different solution must be found for each program point El Context sensitivity Is solution sensitive to the calling context of a function I Contextinsensitive a single solution is computed for each function no matter who calls the function I Contextsensitive different solutions are computed for different chains of callers El Path sensitivity Is solution sensitive to different execution paths of a program I Path sensitive different solutions are computed for different paths from program entry to each statement c56463 4 Scopes of Program Analysis I What code are examined to find the solution I Local analysis a Operate on a straightline sequence of statements a basic block a Often used as basis for more advanced analysis approaches I Regional analysis a Operate on code with limited control flow eg loops conditionals u Useful for specialpurpose optimizations eg loop optimizations I Global intraprocedural analysis a Operate on a single proceduresubroutinefunction is Required by most flowsensitive analysis problems I Wholeprogram interprocedural analysis a Operate on an entire program all sources must be available a Required by context and path sensitive analysis c56463 Common Approaches to Program Analysis n A family of techniques I Data flow analysis operate on controlflow graph in Define a set of data to evaluate at entry and exit of each basic block a evaluate the flow of data between predsucc basic blocks I Constraint based analysis a For each program entity to be analyzed define a set of constraints involving information of interest I Solve the constraint system via mathematical approaches I Abstract interpretation 1 Define a set of data to evaluate at each program point Map each statementconstruct to a finite sequence of semantic actions a Statically interpret each instruction in program execution order I Type and effect systems a Categorize different properties into a collection of typesgroups n lnfer the typegroup of each program entity from how it is used I Techniques differ in algorithmic methods semantic foundations language paradigms c56463 Example Dataflow Analysis Reaching Definitions Example program with labels Controlflow graph y 1 xl1 z12 Bl y 1 X1 while y gt 013 z 1 12 z z y4 y 1 y 115 y 016 An assignment x ai reaches if there is an execution path from entry to j where x was last assigned at i c56463 Reaching Definition Analysis The best solution A y 1 x1 z 12 A while y gt O3 z z y4 yiy15 y 06 A V c56463 y y y y y y y y Solving the dataflow problem Reaching definitions a Domain of analysis I The set of all definition points in a procedurefunction I A definition point cl of variable v reaches CFG point p iff there is a path from cl to p along which v is not redefined I At any CFG point p what definition points can reach p n Reaching definition analysis can be used in I Building dafaflow graphs 1 Provide info where each operand is defined I SSA static single assignment construction n A representation that encodes both control and data flow of a procdure n For each basic block n let I DEDefn definition points whose variables are not redefined in n I DefKilln definitions obscured by redefinition of the same name in n cl Goal evaluate all definition points that can reach entry of n I RDn U DEDefm U RDm DefKillm mepredn c56463 9 Dataflow Analysis Algorithm Computing Reaching Definitions n For each basic block n compute I DEDefn definition points whose variables are not redefined in n l DefKilln definitions obscured by redefinition of the same name in n d Goal evaluate all definition points that can reach entry of n RDn U DEDefm U RDm DefKillm mepredn for each basic block bi compute DEDefbi and DefKillbi RDbi Q for changed true changed changed false for each basic block bi old RDbi RDbi U DEDefm U RDm DefKillm mEpredbi if RDbi old changed true C56463 10 Example solution reaching definition analysis yix1 2212 while ygt03 zzy4 yiy15 y06 DEDef DefKiII RD RD RD Bl 12 564 Q Q Q B2 Q Q Q 1245 1245 B3 45 126 Q 1245 1245 B4 6 1 Q 1245 1245 c56463 Domain 124 5 6 Y2 Z Y Y Example Constraintbased Analysis Loop dependence analysis Example code for i0iltNi for j0jltNj CiNjCi1NjCiNj12 A loop iteration ij depends on another iteration i j if it uses the value computed by i j or if it writes to a common location written by i j If a loop iteration ij depends on iteration i j the ordering of the two iterations cannot be switched C56463 12 Loop dependence analysis Solving a system of equations Example code for i0iltNi for j0jltNj CiNjCi1NjCiNj12 n A loop iteration ij depends on another iteration i j if i j computes the value used by ij that is If Ci Nj Ci1Nj Ci Nj CiNj 1 or Ci Nj CINj refer to the same location I That is if i Nj i1Nj i Nj iNj1 or i Nj iNj c56463 Example abstract interpretation analysis Pointsto analysis Example program with labels struct Cell int val struct Cellquot next h t p h t NULL1 for int i02 iltN3 i4 p new CelliNULL5 if h z NULL6 h t pl7 else tgtnext p t p8 El Define the data to evaluate I A set of locations for each pointer variable I Keep track of constant values for nonpointer variables El Define a semantic action for each statement I Modifies the location set of pointer variables I Allocate new locations in Limit the number of locations for each stmt I Control flow conditionals loops and function calls a Assume all branches are taken when not sure What locations can each pointer variable points to can they point to the same location Abstract interpretation of pointsto locations h t NULL1 i02 gthgt0 tgt0 pgt t I ifiltN3 gtggpgt p new CelliNULL5 h 0 t39gt 0 p W 5 if h z NULL6 39 P e l 1 ht 7 gthgt0tgt0pgtnew5 i4 p gt h gtnew5 t gtnew5 p gt new5 if iltN3 gt h gtnew5 t gtnew5 p gt new5 gt 392 p new Ce iNULL5 h gt0new5 t gt0new5 p gtnew5 if h NULL6 gt h gt0new5 t gt0new5 p gt new5 else tgtnext p t 2 18 i 2 I n7vel5 gtprv7lv5 i4 if iltN3 39 p gt Exit loop if evaluation has stopped changing h gt0new5 t gt0new5 p gt new5 C56463 15 Abstract Interpretation AbstractInterpretationop if isassignmentop modifymemoryfromassignmentmemoryop op else if isconditionalop then AbstractInterpretationcondop AbstractInterpretationtreebranchop AbstractInterpretationfasebranchop else if isloopop then repeat startmonitorachangesmemorystmtsop AbstractInterpretationstmtsop until nothing changes in memorystmtsop else if isproceduralcalop then setupparametersandreturnop AbstractInterpretationbodyop else C56463 16 Example Solution Abstract Interpretation struct Cell int val struct Cellquot next h t p h t NULL1 for int i02 iltN3 i4 p new CeiNULL5 if h z NULL6 h t p7 else tgtnext p t p8 Domain htp gt gt p gt t gt gt t gt gt t gt p gt tgt p gtnew5 tgt p gtnew5 c56463 I I I I I vVvavavavavav M1 M1 A o o O Example type and effect analysis Pointsto analysis Example program With labels El The type domain locations structCell I Each statement that allocates a int val new location structCell next I Each variable that has a location h t p I Examine each statement and ht NULL1 infer a type a group of for int i02 iltN3 i4 locations for each pointer p new Cei NULL5 variable if h NULL16 I Each pointer variable can have h t p7 only a single type no matter else where it appears tgtnext t D How insenSitiVe El If a distinct type is inferred for each expression then analysis is flow sensitive What locations can each pointer variable points to can they point to the same location C56463 18 Applying type and effect approach to points to analysis Example program with labels El struct Cell int val struct Ce next h t p h t NULL I for int i02 iltN3 i4 p new CeiNULL5 if h NULL6 h t p7 else tgtnext p t p8 El c56463 The type domain includes I NULL new5 Examine the program text and union all types locations for each variable htNULL1 n H gtNULLt gtNULL I p new CelliNULL5 n P gt new5 I h t p7 and t p8 n Typep is a subset of Typeh n Typep is a subset of Typet Result I hgt NULLnew5 I tgt NULL new5 I pgt new5 Key define typing rules Interprocedural Analysis and Abstract Interpretation Outline Interprocedural analysis I control flow graph MVP Meet over Valid Paths I Making context explicit in Context based on call strings n Context based on assumption sets El Abstract interpretation c56463 Control ow graph for a Whole program El At each function definition proc px I Create two special CFG nodes i initp and finalp I Build CFG for the function body 1 Use initp as the function entry node 1 Connect every return node to finalp At each function call to px with I Split the original function call into two stmts 1 Enter px before making the call and exit px after the call exits I Connect enter px gtinitp finalp gt exit px I Connect enter px gt exit px to allow the flow of extra context info Three kinds of CFG edges I Intraprocedural internal controlflow within a procedure I Procedure calls from enter px to initp I Procedure returns from finalp to exit px c56463 Interprocedural CFggrgmple B0 initfib fibz 1 V B3t1eXit fibz 1 enter f1bz 2 int fibint Z if Z lt 3 then return 1 else return fibZ 1 fibZ 2 Main program return fib15 A0enter fib 15 B4t2eXit fib 2 2 return t1t A1 t exit fib15 B6 fina1fib a Problem matching between function calls and returns c56463 4 Extending monotone frameworks El Monotone frameworks consists of I A complete lattice Ls that satisfies the Ascending Chain Condition I A set F of monotone transfer functions from L to L that 1 contains the identity function and 1 is closed under function composition El Transfer functions for procedure definitions I For simplicity both initp and finalp have identity transfer functions El Transfer functions for procedure calls I For procedure entry assign values to formal parameters I For procedure exit assign return values to outside c56463 Problem calling context upon return m B0 initfib fibz 1 V B3t1eXit fibz l enter f1bz 2 int fibint Z if Z lt 3 then return 1 else return fibZ l fibZ Z Main program return fib15 A0enter fib 15 B4t2eXit fib 2 2 return t1t A1 t exit fib15 B6 fina1fib Matching between function calls an returns l Calculating solutions on nonexisting paths could seriously detriment precision n Eg enter fibz2 gt initfib gt gt exit fibzl gt c56463 6 MVP Meet over Valid Paths a Problem matching procedure entries and exits function calls and returns a A complete path must I Have proper nesting of procedure entries and exits I A procedure always return to the point immediately after it is called a A valid path must I Start at the entry node of the main program I All the procedure exits match the corresponding entries I Some procedures may be entered but not yet exited n The MVP solution I At each program point t the solution for t is u MVPt A solp p is a valid path to t c56463 7 Making Context Explicit El Context sensitive analysis I Maintain separate solutions for different callers of a function El Extending the monotone framework I Starting point context insensitive II A complete lattice Ls that satisfies the Ascending Chain Condition L PowerD where D is the domain of each solution 1 A set F of monotone transfer functions from L to L I Extension 1 L Power D C where C includes all calling contexts in F L gt L a separate subsolution is calculated for each calling context F procedure entry attach caller info to incoming solution F procedure exit match caller info eliminate solution for invalid paths c56463 8 Different Kinds of Context El Call strings contexts based on control flow I Remember a list of procedure calls leading to the current program point a Call strings of unbounded length remember all the preceding calls 1 Call strings of bounded length k remember only the last k calls El Assumption sets contexts based on data flow Assumption sets 1 Use the solution before entering proc px as calling context eg each context makes distinct presumptions about values of function parameters I Large vs small assumption sets a How large is the context use the entire solution or pick a single constraint from the solution c56463 9 Example Context sensitive Analysis m B0 initfib fibz 1 V B3t1eXit fibz 1 enter f1bz 2 int fibint Z if Z lt 3 then return 1 else return fibZ 1 fibZ 2 Main program return fib15 A0enter fib 15 B4t2eXit fib 2 2 return t1t A1 t exit fib15 B6 fina1fib a Range analysis for each variable reference x is its value gt or lt a constant value Le x gt x1 zltn2 c56463 Example Range Analysis Variables Xz t1 t2 fib t Contexts A0 B2 B3n0ne Domain Variables ltn n gtnany A0 none none none none 50 none A0z15 BZB3 A0z15BZzgt2 A0z15BZzgt2 z z B3zgt1 B3zgt1 Bl none A0z15BZB3 A0z15BZzgt2 A0z15BZzgt2 z z B3zgt1 B3zgt1 52 none A0z15 BZB3 A0z15BZB3zgt A0z15BZB3zgt z zgt3 3 3 53 none A0z15t1 A0z15t11 A0z15t1gt1 zt1 BZB3zgt3t1 BZB3zgt3t11 BZB3zgt3t1gt1 54 none A0z15t1t2B A0z15t1t21B A0z15t1t2gt1B ztlt2 2B3zgt3t1t2 2B3zgt3t1t21 2B3zgt3t1t2gt1 B5 nose BZB3zlt2 BZ22 B3zlt2 BZ22 B3zlt2 2 B6 nonezfib A0z15fibBZ A0z15fibgt1BZ A0z15fibgt1BZ B3zanyfib1 B3zanyfibgt1 B3zanyfibgt1 A1 nonet nonet nonet gt1 nonetgt1 c56463 Foundations of Abstract Interpretation El Definition from Wikipedia I abstract interpretation is a theory of sound approximation of the semantics of computer programs It can be viewed as a partial execution of a computer program without performing all the calculations a Outline I Monotone frameworks n A complete lattice Ls that satisfies the Ascending Chain Condition 1 A set F of monotone transfer functions from L to L that contains the identity function and is closed under function composition I Galois connections closuresand Moore families I Soundness and completeness of operations on abstract data I Soundness and completeness of execution trace computation C56463 12 Galois Connections a Two complete lattices I C the concrete execution data a The execution of the entire program a Infinite and impossible to model precisely I A the abstract execution data a Properties abstractions of the concrete data a The solution space domain of static program analysis I For complete lattices C and A a Galois connection is I A pair of monotonic functions 0L CgtA y A gt C I For all a E A and c E C c s y 0LC and 0ty a s a I Is Written as Clt0LygtA C56463 13 Galois Connections 2 El y and 0c are inverse maps of each other s image I For all CEyAcycxc for all Y aEcxC a0iya 1234 I The maps 0i are 1357 homomorphism mappings between C and A 1723 maSW1d El Galois connections are closed under 2 4 1 none I Composition product and so on ii Each instruction performs an action f CgtC I Can use 0c and y to define an abstract transfer function f AgtA for each f CgtC C56463 14 Closure Maps I For Clt0tygtA it is common that A g C This means A embeds into C as a sublattice I A s elements name distinguished sets in C n A closure map defines the embedding of A within C Definition pCgtC is a closure map if it is I Monotonic V01026 C of s 02 gt pC1s p02 I extensive V0 5 C c s pc I idempotent VCE C ppc 90 03 p p p 1234 a all 1W 123 135 eve Odd 24 1 110116 1 Every Galois connection CltaygtA defines a closure map 0 39 Y 2 Every closure map pC gtCdefines the Galois connection CltpidgtpC C56463 15 Moore Families El Given C can we define a closure map on it by choosing some elements of C I Yes if the elements we select are closed under greatestlowerbounds meet operation I That is the new set of elements forms a complete lattice ii Definition M g C is a Moore family iff for all 8 g M 8 E M I We can define a closure map as pc c E M lo 5 c I That is we map each element in C to the closest abstraction approximation in M El For each closure map pCgtC its image pC is a Moore family Given C we can define an abstract interpretation by selecting some M g C that is a Moore family C56463 16 Closed Binary Relations El El Often the solution of an analysis is a power set of its domain I The Galois connection can be written as PowerDltcxygtA Given unordered set D and complete lattice A it is natural to relate the elements in D to those in A by a binary relation R Q D A st I da e R or cl R a cl R a means d has property a I Example Dlnt Anonenegposzerononnegnonposany n Then 2 R nonneg 2 R pos and 2 R any The adjoint function y AgtPowerDcan be defined as I ya d E D Id R a Eg y nonneg012 I If R defines a Galois collection then yA defines a Moore family Proposition RQDA defines a Galois connection between PowerD A iff I R is U cosed c R a and a s a imply c R a I Ris GcosedcRquotalcRa C56463 17 Concrete and Abstract Operations El Now that we know how to model a solution space via abstraction function or C gt A I We must model concrete computation steps fCgtC by abstract computation steps fA gt A El Example we have concrete domain Nat and concrete operation succ Nat gt Nat defined as succnn1 I abstract domain Parity any even odd none I abstract operation succParity gt Parity defined as succevenodd succoddeven succanyany succnonenone I succ must be consistent sound with respect to succ if n Rn a then succn Rn succa 1 where Rn g Nat Parity relates numbers to their parities eg 2 Rn even 5 Rn odd etc C56463 18 Sound Approximation El Given I Galois connection Clt0LygtA and I functionsf CgtC and fAgt A f is a sound approximation of f iff I For all c E C afc s fOLC I For all a E A fya s yfa El That is 0L defines a semihomomorphism with respect to f and f Oi gt 0ic f f fC gt 0160 5 fOKCD C56463 19 Sound Approximation Example Given I Galois connection PowerNatltaygtParity and I Concrete transfer function succ NatgtNat succS n 1 n E S I Abstract transfer function succ Parity gt Parity succevenodd succoddeven succanyany succnonenone El succ is a sound approximation of succ I For all c E Nat xsuccc succcxc or 26 gt even i succ l succ 37 4r odd C56463 20 Synthesizing f from f El Given CltorygtA and function f CgtC the most precise fAgtA that is sound with respect to f is I f best a 0c f y a El Proposition f is sound with respect to f iff I For all a E A f besta s fa I Of course fbest has a mathematical definition not an algorithmic one fbest might not be finitely computable El Parity example continued I succbesteven 0c succ y even or succ 2n I n20 or 2n1 n20 2 odd I Question what about other operators on Nat eg C56463 21 Completeness of Approximationskip Given CltaygtA and function f CgtC Function f AgtA is sound with respect tof iff I For all c E C 0L f c s f cxc For all a e A fya s yfa Function f AgtA is forwardsy complete with respect to f iff For all a e A fya yfa I That is yA is closed underf fyAQ yA Function f AgtA is backwardsa complete with respect to f iff I For all c E C 0L f c f cxc I That is or partitions C into equivalence classes 0LC 0LC implies 0cfCocfC n For an f to be forwards or backwards complete it must equal fbest0i f y a I The structure of CltcxygtA and f CgtC determines whether f is complete C56463 22 Transfer Functions and Computation steps El Each program transition from program point pi to pj has an associated transfer function fijCgtC or fijAgt A which describes the associated computation I This defines a computation step of the form pis gt pjfijs El Example I Assignment p0xx1 p1 has the transfer function f01ltxngt ltxn1gt I For multiple transitions in conditionals attach a transfer function to each possible transition branch to filter the data that arrives at a program point eg p0 cases xsy p1 yyx ysx p2xxy end i sx s sy then 5 else bot filter out 5 unless sx s sy f sy s sx then 5 else bot filter out 5 unless sy s sx El fp1s 1 fp2s C56463 23 Execution Traces El An execution trace is a possibly infinite sequence p0SOgtp1s1gtgtpisigt st l for all i202 piSi gt psuccifisucciSi No si equals bot P0 while x 1 P1 if Evenx P2 x x div2 P3 else x 3x 1 P5 exit c56463 Two concrete traces piv means pixv p04 p14 p24 p02 p12 p22 p01 p41 p06 p16 p26 p03 p13 p23 p010 p41 24 Using Approximation to build abstract traces Abstract over approximating trace p0even 1 Each concrete p1 even transition is generated DZ GVG by an fij poiany 2 Each abstract transition AF any is generated by the p4odd i corresponding fij p3odd a Each concrete transition pisgt pjfijs is reproduced by a corresponding abstract transition piagtpjfija where 36 ya El The traces embedded in the abstract trace tree cover simulate the concrete traces c56463 25 Shape Analysis El Goal I To obtain a finite representation of the memory storage El The analysis result can be used for I Detection of pointer aliasing I Detection of sharing between structures I Software development tools 1 Detection of pointer errors eg dereferences of nilpointers I Program verification 1 Egreverse transforms a noncyclic list to a noncyclic list C56463 26 The Concrete Solution Space El Model the memory stack and heap I Storage of local variables Stack Var gt Value U Loc Map each local variable into a value or a unique location I The heap storage Heap Loc Sel gt Value u Loc Map pairs of locations and selectors to values or locations El Model the operational semantics of programs I Program state State ProgramPoint Stack Heap Example p1 x3yLy Lyva5 is a program state I Each statement modifies Stack and Heap of the previous state a Stmt State gt State C56463 27 Building Abstract Domains El Given an unordered set D of concrete data values we might ask I quotWhat are the properties about D that I Wish to calculate I Can Ireate these properties a e A to elements d e D via a UGcosed binary relation R DA II Given a set A and a binary relation R D A I Define y AgtPowerD as ya d E D d R a I Define partial ordering on A a s a iff ya s ya u If there are distinct a and a such that yaya then merge them to force U closure I Ensure that yA is a Moore family by adding greatestIowerbound elements to A as needed a This forces Gclosure I Use the existing machinery to define the Galois connection between PowerD and A C56463 28 Abstracting the Program State n Build a binary relation Rd DataAbsData I Rv Value gt AbsValue Rl Loc gt AbsLoc I May ignore the values of nonpointer variables El Build induced Galois connection PowerDataltocygtAbsData we can I Build Galois connections that abstract the concrete data ltxi vigt Rs ltxi aigt iff vi Rd ai Example ltx3 y4gt Rs ltxany yanygt I A program point is abstracted to itself p Rp p the abstract domain of program points is ProgramPoint U top bot to make it a complete lattice I Finally we can relate each concrete state to an abstract one ps Rs p s iff p p and 5 Rs 5 C56463 29 Shape Graphs El Shape analysis uses a shape graph to abstract the memory storage I Graph nodes denote a finite number of abstract locations in Aloc Nx l Nx is pointed to by a set of local variables U Nq Nx the node represents all concrete Locations referred to by variables In X N absUactsunnnaryloca onache herloca ons 1 Each graph node abstracts a distinctive set of concrete Locations If variables x and y may be aliased they must share a single graph node I A graph edge sel connect nodes n1 and n2 if n2 is pointed to by n1 sel X M2 next c56463 30 next Abstraction of Program States Abstraction of memory storage I Abstract Stack AbsStack Var gt ALoc Map each pointer variable into a unique abstract location a shape graph node I Abstract heap AbsHeap ALoc Sel gt ALoc Mapping pairs of abs locations and selectors to abs locations I Sharing information in IS ALoc gt yes no For each abstract location in the shape graph is it shared by pointers in the heap u If SNx yes then Nx must have an incoming edge from Nq or have more than one incoming edges El Transfer functions PAbsState gt PAbsState I Program state AbsStatezProgramPoint AbsStack AbsHeap IS I Each statement modifies mappings in the previous state C56463 31 Transfer functions1 El x nil F SHIS S H IS where S H IS is obtained from SHIS by n Removing X from all mappings killing all previous info about X n Merging all N nodes sell se12 SHIS S39IH39IIS39 C56463 32 Transfer functions2 El X y I F SHIS S H IS Where a S H IS is otained by modifying mappings for X to be identical to those for y sell y se12 SIHIIS S H39IS C56463 33 Data ow analysis Theory and Applications c56463 Control ow graph El Graphical representation of runtime control flow paths I Nodes of graph basic blocks straightline computations I Edges of graph flows of control n Useful for collecting information about computation I Detect loops remove redundant computations register allocation instruction scheduling ii Alternative CFG Each node contains a single statement i0 while ilt50 t1b2 aat1 t1b2 ii1 aat1 i I 39 c56463 Building control ow graphs Identifying basic blocks El Input a sequence of threeaddress statements El Output a list of basic blocks El Method I Determine each statement that starts a new basic block including a The first statement of the input sequence a Any statement that is the target of a goto statement a Any statement that immediately follows a goto statement I Each basic block consists of n A starting statement SO leader of the basic block I All statements following SO up to but not including the next starting statement or the end of input I quotquot quoti Starting statements CsOifilt50gotosl 0 goto 52 50 slt1b2 goto 82 a a t1 Sl goto 50 52 C 52 c56463 Building control ow graphs Identify all the basic blocks I Create a flow graph node for each basic block El For each basic block Bl I If Bl ends with a jump to a statement that starts basic block B2 create an edge from Bl to B2 I If Bl does not end with an unconditional jump create an edge from B1 to the basic block that immediately follows B1 in the original evaluation order c l C so ifi lt 50 goto sl goto 52 W SO if i lt 50 goto sl sltlb2 aat1 sltlb 2 E 52 goto 50 c56463 Example Data ow Live variable analysis El A data flow analysis problem I A variable v is live at CFG point p iff there is a path from p to a use of v along which v is not redefined I At any CFG point p what variables are alive a Live variable analysis can be used in I Global register allocation 1 Dead variables no longer need to be in registers I Useless store elimination a Dead variable don t need to be stored back to memory I Uninitialized variable detection 3 No variable should be alive at program entry point c56463 5 Computing live variables El For each basic block n let I UEVarnvariabIes used before any definition in n l VarKiIInvariabes defined modified in n killed by n for each basic block nSlSZS3Sk VarKiII Q UEVarn Q for i 1 to k suppose Si is x y op 2quot if y 62 VarKiII UEVarn UEVarn U y if z 62 VarKiII UEVarn UEVarn U z VarKiII VarKiII U X c56463 Computingliye variables A mab a Domain mab I All variables inside a function n For each basic block n let 5 pcd C qab l UEVarn r39Cd r Cd vars used before defined 39 I VarKin t18 f 17 vars defined killed by n D e E e39a Goal evaluate vars alive on 51 t Cdf entry to and at from n u39e u39e LiveOutnUmesuccnLiveInm LiveInmUEVarm o F Vab LiveOutmVarKiIm gt LiveOutn U mEsuccn m H UEVarm U G 3er LiveOutmVarKiIm c56463 7 Algorithm computing live variables n For each basic block n let I UEVarnvariables used before any definition in n I VarKillnvariables defined modified in n killed by n Goal evaluate names of variables alive on exit from n I LiveOutn U UEVarm U LiveOutm VarKillm mesucc n for each basic block bi compute UEVarbi and VarKillbi LiveOutbi Q for changed true changed changed false for each basic block bi old LiveOutbi LiveOutbi U UEVarm U LiveOutm VarKillm mesuccbi if LiveOutbi old changed true c56463 Solution Computinghve variables a Domain A mab abcdefmnpqrstuvw nab UE Vark Live LiveOu LiveOut p Cd C q a db A ab mn Q abcd abcd rcd r C f f A A B cd pr Q abcd abcd eb18 ea17 C b g b d b d D I I a I qlr a C a C I s ab E t cd cd I f uef uef D ab es Q abcd abcd f u f F Vab E ac etu Q abcd abcd wcd df F ab vw Q abcd abcd V cd f G G ab mn Q Q Q ncd cd c56463 9 Another Example Available Expressions Analysis El The aim of the Available Expressions Analysis is to determine I For each program point which expressions must have already been computed and not later modified on all paths to the program point I Example Optimized code x ab 1 x ab1 yab2 yab2 while ygt ab 3 while ygt x 3 aa14 aa14 x ab 5 x ab5 C56463 10 Available Expression Analysis a Domain of analysis A miab I All expressions within a bcd function B e n For each basic block n let pab C qab I DEEXDU ecd 1Cd Exps evgluadtgginvti ighout any 0 eran re EEpKiIKn e b18 e a17 Exps whose operands are D sab E t cd redefined exps killed by n aef bef Goal evaluate exps available on all paths entering n Wab AvaiIInn meprednAvaiOutm F xef AvailOutm DEexpmU AvailInmEprilm gt G yab AvaiIInn mEpredn ccd c56463 DEexpm U AvailInmEprilm Algorithm computing available expressions El For each basic block n let I DEexpnexpressions evaluated without any operand redefined I EpriIInexpressions whose operands are redefined in n Goal evaluate expressions available from entry to n AvaiIInn mEprednDEeXpm U AvailInmEprilm for each basic block bi compute DEexpbi and Epribi AvaiIInbi isEntrybi Q DomainExp for changed true changed changed false for each basic block bi old Avaibi AvaiIInbi mEpredbiDEeXpm U AvailInmEpriIm if AvailInbi old changed true C56463 12 Solution Available Expression Analysis Domain ab1 cd2 A mab b183ef4a175 bcd DEexp EpriI Avail Avail B 39ab A 2 L3 o o p ab C q ecd ecd 39 3 12 4 12345 2 eb18 e a17 DS39ab E t39 cd C 1392 4 12345 2 ae bef D 34 145 12345 12 Wab E 245 134 12345 12 F Xef F 14 Q 12345 24 y ab 3 12 2 12345 12 G ccd c56463 Iterative data ow algorithm for each basic block bi compute Genbi and Kibi Resultbi Q or Domain for changed true changed changed false for each basic block bi old Resultbi Resultbi D or U mEpredbi or succbi Genm U Resultm Kim if Resultbi old changed true n Iterative evaluation of result sets until a fixed point is reached I Does the algorithm always terminate a If the result sets are bounded and grow monotonically then yes Otherwise no u Fixedpoint solution is independent of evaluation order I What answer does the algorithm compute 1 Unique fixedpoint solution 1 The meetoveraIIpaths solution I How long does it take the algorithm to terminate a Depends on traversing order of basic blocks C56463 14 Traversing order of basic blocks n Facilitate fast convergence to the fixed point postorder n Postorder traversal I Visits as many of a nodes successors as possible before visiting the node I Used in backward dataflow analysis a Reverse postorder traversal I Visits as many of a node s predecessors as possible before visiting the node a I Used in forward dataflow Reverse anal sis I postorder y C56463 15 The Overall Pattern II Each dataflow analysis takes the form Inputn Q if n is program entryexit A mEFlown Resultm Resultn fn Inputn I where A is n or U may vs must analysis a May analysis detect properties satisfied by at least one path U 1 Must analysis detect properties satisfied by all pathsm I Flown is either predn or succn forward vs backward flow 1 Forward flow data flow forward along controlflow edges Inputn is data entering n Result is data exiting n Inputn is Q if n is program entry 1 Backward flow data flow backward along controlflow edges Inputn is data exiting n Result is data entering n Inputn is Q if n is program exit I Function fn is the transfer function associated with each block n otherwise c56463 The Mathematical Foundation of Data ow Analysis El Mathematical formulation of dataflow analysis I The property space L is used to represent the data flow domain information I The combination operator A PL a L is used to combine information from different paths n A set P is an ordered set if a partial order s can be defined st VXyZEP I x s X reflexive I If x S y and y S x then x y asymmetric I If x s y and y s 2 implies x s z transitive n Example PowerL with Q define the partial order C56463 17 Upper and lower bounds Given an ordered set P s for each S Q P El Upper bound I x is an upper bound of S if x e P and VyES y s x I x is the least upper bound of S if 1 x is an upper bound of S and 1 x s y for all upper bounds y of S I The join operation V n V S is the least upper bound of S 1 X V y is the least upper bound of xy Lower bound I x is a lower bound of S ifx e P and VyES x s y I x is the greatest lower bound of S if n X is an lower bound of S and 1 y s x for all lower bounds y of S I The meet operation A 1 A S is the least upper bound of S n x A y is the least upper bound of xy c56463 Lattices n An ordered set L s V A is a lattice I If x A y and x V y exist for all xyEL I An lattice Ls A is a complete lattice if I Each subset Y Q L has a least upper bound and a greatest lower bound 1 LeastUpperBoundY VmEY m u GreatestLowerBoundY A mEY m All finite lattices are complete Example lattice that is not complete the set of all integers I I For any X yEI x A y minxy x V y maxxy I But LeastUpperBoundI does not exist I I U oo oo is a complete lattice Each complete lattice has I A top element the least element I A bottom element the greatest element EIEI El C56463 19 Chains n A set S is a chain if VXyES y s x or x s y El A set S has no infinite chains if every chain in S is finite n A set S satisfies the finite ascending chain condition if I For all sequences x1 s x2 s there exists n such that u Xn xn1 I That is all chains in 8 have an finite upper bound I A complete lattice L satisfies the finite ascending chain condition if each ascending chain of L eventually stabilizes I If I15 I2 5 IS 5 then there is an upper bound In n1n2 I This means starting from an arbitrary element e E L one can only increase e by a finite number of times before reaching an upper bound C56463 20 Application to Data ow Analysis El Dataflow information will be lattice values I Transfer functions operate on lattice values I Solution algorithm will generate increasing sequence of values at each program point I Ascending chain condition will ensure termination El Can use V join or A meet to combine values at control flow join points C56463 21 Example Dataflow Analysis El Reaching Definitions I L PowerAssignments n L is partially ordered by subset inclusion s is subset relation V is set union n The least upper bound join operation is set union n The least top element is o I L satisfies the finite ascending chain condition because Assignments is finite El What about live variable analysis and available expression analysis C56463 22 Transfer Functions El Each basic block n in a dataflow analysis defines a transfer function fn on the property space L fnLgtL Outn fn lnn The set of transfer functions F over L must satisfy the following conditions I F contains the identity function I F is closed under composition of functions a Composition of monotone functions are also monotone All transfer functions are monotone if I For each e1 e2 E L if e1 5 e2 then fne1 s fne2 Sometimes transfer functions are distributive over the joinmeet op fX A y fX A W I Distributivity implies monotonicity C56463 23 Reaching De nitions I P power set of all definitions in program all subsets of the set of definitions in program I All transfer functions have the form fX GEN U X KILL El Does it satisfy required lattice properties I Does it support the required operations a Three operations 5 V A bottom and top I Does it satisfy finite ascending chain condition I Are transfer functions monotone distributive I Are they valid transfer functions 1 Dfx Q U x Q is the identity function a What about composition I Are they monotone n if x G y then GEN U X KILL G GEN U y KILL I Are they distributive GEN U X KILL U GEN U y KILL GEN U x U y KILL c56463 24 Reaching De nitions Composition and Distributivity El Composition given two transfer functions f1 and f2 I f1x a1 U xbl and f2x a2 U xbz f1f2x can be expressed as a U X b f1f2X 81 U 82 U Xb2 bl a1 U 32 39 b1 U X39bz 39 bl a1 U 82 b1 U X39bz bl a1 U 32 39 b1 U X39b2 U b1 I Let a a1 U a2 b1 and b b2 U blithen f1f2x a U X b I Distributivity fX U y fx U fy fX U W a U X b U a U y b aUX bUy baUXUy b fx U y C56463 25 Monotone Frameworks n A monotone framework consists of I A complete lattice Ls that satisfies the Ascending Chain Condition I A set F of monotone functions from L to L that 3 contains the identity function and n is closed under function composition I A distributive framework is a monotone framework Ls AF that additionally satisfies I All functionsf in F are required to be distributive n f1Al2fl1Afl2 I A bitvector framework is a monotone framework that I L PowerD where D is a finite set I Each transfer function in F has the format Gen U ResKill I All bitvector frameworks are distributive I Not all monotone frameworks are distributive I Example nondistributive framework constant propagation C56463 26 General Result All GENKILL transfer function frameworks satisfy Identity I Composition I Distributivity Properties C56463 27 Workhst Algorithm for Solving Data ow Equations For each basic block n do Inn Q or Domain Outn fnInn Inno Q Outn fn0Inn0 worklist all basic blocks entryexit block n0 while worklist do remove a node n from worklist Inn m or U m in predn or succn Outm Outn fnInn if Outn changed then worklist worklist U succn or predn C56463 28 Meet Over Paths Solution El What is the ideal solution for dataflow analysis El Consider a path p n0 n1 nkn I for all i ni E flowni1 El The solution must take this path into account fpt0p fnkfnk1fn1fn0top s Inn El So the solution must have the property that Afp top p is a path to n s Inn andideaHy Afp top p is a path to n Inn C56463 29 Distributivity Distributivity preserves control flow precision I If framework is distributive then worklist algorithm produces the meet over paths solution I For each basic block n Afp top p is a path to n Inn C56463 30 Lack of Distributivity Example El Constant Calculator a Flat Lattice on Integers El Actual lattice records a single value for each variable I Example element ae3 b92 c95 C56463 31 Lack of Distributivity Anomaly g a2 a3 b3 b2 b3 2192 2193 bez aQTOP beTOP Lack of Distributivity Imprecision C ab aeTOR beTOP 05 more precise aTOP beTOP cTOP C56463 32 HOW to Make Analysis Distributive El Keep combinations of values on different paths a2 a3 b3 b2 2192 be3 2193 b92 2192 be3 2193 b92 cab 2192 b93395 2193 b92c5 C56463 33 Issues El Basically simulating all combinations of values in all executions I Exponential blowup I Nontermination because of infinite ascending chains El Non termination solution I Use widening operator to eliminate blowup can make it work at granularity of variables I Lose precision in many cases c56463 34 Termination Argument Why does algorithm terminate El For each basic block n I Sequence of values taken on by Inn or Outn is a chain I If values stop increasing worklist empties and algorithm terminates El If lattice has ascending chain property algorithm terminates I Algorithm terminates for finite lattices I For lattices without ascending chain property use widening operator C56463 35 Widening Operators El Detect lattice values that may be part of an infinitely ascending chain a Artificially raise value to least upper bound of chain El Example I Lattice is set of all subsets of integers I Could be used to collect possible values taken on by variable during execution of program I Widening operator might raise all sets of size n or greater to Bottom likely to be useful for loops C56463 36 General Sources of Imprecision El Abstraction Imprecision I Concrete values integers abstracted as lattice values eg use gt0 0 lt0 to approximate values of a variable I Lattice values less precise than execution values I Abstraction function throws away information El Control Flow Imprecision I One lattice value for all possible control flow paths I Analysis result has a single lattice value to summarize results of multiple concrete executions I Joinmeet operation moves up in lattice to combine values from different execution paths I Typically if x s y then x is more precise than y C56463 37 More about data ow analysis In Other data flow problems I Reaching definition analysis I A definition point d of variable v reaches CFG point p iff there is a path from d to p along which v is not redefined a At any CFG point p what definition points can reach p I Very busy expression analysis a An expression e is very busy at a CFG point p if it is evaluated on every path leaving p and evaluating e at p yields the same result a At any CFG point p what expressions are very busy I Constant propagation analysis a A variablevalue pair vc is valid at a CFG point p if on every path from procedure entry to p variable v has value c a At any CFG point p what variables have constants I Sign analysis a A variablesign gt00lt0 pair vs is valud at a CFG point p is on every path from procedure entry to p variable v has sign 5 C56463 38 ust Management S 6463 Lecture 8 Prof William Winsborough February 13 2006 Business I Next week we will continue discussing the paper posted for today N Li W Winsborough and J C Mitchell Distributed Credential Chain Discovery in Trust Management Journal of Computer Security 1113586 February 2003 I Syropsis due 220 should discuss pages 1936 sections 47 lquot Focuses on finding credential chains when credential storage is distributed I Only one extended synopsis will be due for this paper lquot Due March 1 l Make it a really good extended synopsis February 13 2006 Winsborough CS 6463 Lecture 8 2 v 1 Today s Outline I KeyNote adequacy discussion I Discussion of KeyNote projects I Start discussing RT0 February 13 2006 Winsborough CS 6463 Lecture 8 KeyNote s Adquacy I Determining whether a principal has any authorizations according to a given policy seems to be undecidable 2 Encode Hilbert s Tenth Problem in conditions Hilbert s Tenth Problem Determination of the solvability of a Diophantine equation Given a Diophantine equation with any number of unknown quantities and with rational integral numerical coefficients The problem is to devise a process according to which it can be determined by a finite number of operations whether the equation is solvable in rational integers htt lo ic dmirasru umatH10Pbookindexhtml httpwwwcscmuedulblumcourses acFLAC Pro39ectsJoeRoth ac pro39ect finalpdf I Other problems with this design 1 How are credentials found 31 Who stores them February 13 2006 Winsborough CS 6463 Lecture 8 4 KeyNotebased Project Ideas l Certainly one could build a distributed application using KeyNote as the basis of a course project I Such a project would need to be organized around testing some hypothesis about the suitability of KeyNote for solving some identifiable group of authorization problems February 13 2006 Winsborough CS 6463 Lecture 8 5 Policy Language Wish List I Decentralize authority to define attributes i Utilize policy and credentials from many sources I Delegation of attribute authority 7 To specific principals a To principals with certain attributes I Inference of attributes L Eg derive access rights based on roles or other characteristics I Intersection of attributes I Parameterization I Support for thresholds separation of duty February 13 2006 Winsborough CS 6463 Lecture 8 6 252 if Rolebased Trust Management RT I A family of credential policy languages l Simplest RTo has no parameterization thresholds or separation of duty I RTO example student discount subscription l EPubstudentDiscount lt StateUstudent l StateUstudent lt URegistrarfulltimeLoad l StateUstudent lt URegistrarparttimeLoad l URegistrarparttimeLoad lt Alice February 13 2006 Winsborough CS 6463 Lecture 8 252 i Rolebased Trust Management RT I A family of credential policy languages 7 l Simplest RTo has no parameterization thresholds or separation of duty I RTO example student discount subscription l EPubstudentDiscount lt StateUstudent l StateUstudent lt URegistrarfulltimeLoad l StateUstudent lt URegistrarparttimeLoad l URegistrarparttimeLoad lt Alice I Credential chain proves authorization February 13 2006 Winsborough CS 6463 Lecture 8 252 Example Attributebased Delegation l Accepting student ID from any university l l EPubstudentDiscount lt FABaccreditedstudent l1 fl FABaccredited lt StateU l1 fl StateUstudent lt URegistrarfulltimeLoad 1 StateUstudent lt URegistrarparttimeLoad 1 URegistrarparttimeLoad lt Alice February 13 2006 Winsborough CS 6463 Lecture 8 252 77 Example Expressivity in Credentials I Deferring a Guaranteed Student Loan BankWondeferGSL lt FABaccreditedfutimeStudent FABaccredited lt StateU 7 StateUfutimeStudent lt URegistrarfutimeLoad StateUfutimeStudent lt URegistrarparttimeLoad m StateUgradOfficerpthandidate at URegistrarparttimeLoad lt Bob 7 StateUgradOfficer lt Carol 7 Carolpthandidate lt Bob February 13 2006 Winsborough CS 6463 Lecture 8 10 RTO Syntax I Basic structure is a role ie an attribute Ar A is a principal authority for Ar r is a role name I Four types of policy statement i i Ar lt D Role Ar contains principal D as a member or Ar lt Br1 Ar contains role Br1 as a subset Ar lt Ar1r2 Ar contains Br2 as a subset for each B in Ar1 ii Ar lt A1r1n A2r2 Ar contains the intersection I A credential is a statement signed by A the credential issuer and the authority over Ar I The first 3 statement types give a language equivalent to pure SDSI February 13 2006 Winsborough CS 6463 Lecture 8 1 1 Setbased Semantics for RTO l Given as set of credentials C the semantics of C is 5C Role gt Entity given by the least function rmem Role gt Entity that satisfies the following system of set inequalities rmemAr 2 exprrmeme Ar lt e e C I Where i exprrmemB B L exprrmemAr rmemAr l7 exprrmemAr1r2 U rmemBr2 B E rmemArl l exprrmemf nf n n f n exprrmemf 1 2 k 1ltjltk February 13 2006 Winsborough CS 6463 Lecture 8 12 LogicProgramming Semantics I Four credential types a Ar lt D type 1 mA r D U Ar lt Br1 type 2 mA r X mB r1 X a Ar lt Ar1r2 type 3 mA r X mA r1 Y mY r2 X D Ar lt A1r1m A2r2 m m Akrk type 4 mA r X mA1 r1 X mAk rk X February 13 2006 Winsborough CS 6463 Lecture 8 Credential Chain Discovery I Outline l Sound and complete evaluation model Based on graphical model credential graph 7 l Efficient search for proof of authorization l Provides a basis for discovering chains when credentials are stored in a distributed manner Evaluation steps can be interleaved with credential retrieval steps February 13 2006 Winsborough CS 6463 Lecture 8 14 Example Student ACM Discount I EPubstudentACM lt EOrgstudent m ACMmember I EOrgstudent lt EOrguniversitystudent Credential Discovered in Backward Direction I EOrguniversity lt FABaccredited FABaccredited lt StateU StateUstudent lt URegistrarparttimeLoad URegistrarparttimeLoad lt Alice Credential Discovered in Forward Direction ACMmember lt Alice February 13 2006 Winsborough CS 6463 Lecture 8 U Credential Graph EPub gives a double subscription discount Type 1 FABaccredited StateU Type 2 EOrguniversity FABaccredited Type 3 EOrgstudent EOrguniversitystudent Type 4 EPubstudentacm EOrgstudent n ACMmember EOrg student Key TCredential ISummary February 13 2006 EOrguniversity EOrguniversitystudent FAB accredited i StateU StateUstudent URegistrarparttimeLoad Winsborough CS 6463 Lecture 8 EPubstudentacm EOrgstudent n ACMmember At ACMmember Alice Credential Graph EPub gives a double subscription discount Organizes Chain Discovery Ar EOrgstudcnt EOrgunivcrsity EOrgunivcrsitystudcnt FABaccrcditcd Key StateU Stathstudcnt T Credential Discovered by EPub in Forward Direction UchistrarparttimeLoad T Credential Discovered by Alice in Backward Direction Summary Edge February 13 2006 Winsborough CS 6463 Lecture 8 EPub studentacm EOrgstudent n ACMmember ACMmcmbcr Alice Arrange thenB 0 S W C Lot L 4quot 5quot 4 H13 0quot 44 plan The k weaves o a plane dam L L is Called la Wheat 4 39 1 Aeg3 C e a 3 0 ALL chumsB of M m lacs an o The LunLI39m39lOn c l WV7 of an ctrNara 04ka is verh m 0690 when oAu 5 S up 4 no we am pm Mmal 94 Samu PM and no he Cm are fanlg lemma i vcr k as a 40 is or am kg 2 0 0 39n t q u h k cm u o 0322 E1 y Add 3 4 u is me Rug i W inkrSedm a no 33 an 02quot 0quot MN ii on A an uhot hl vert m 35 log gt halfoh 5 ARM MD A Raw 1 gmquot quot13 00 t Spin14M 0 4Qal have at 0quot 392 Fm 4i 492321 0an W 9amp hfbk n 9 901374 Fun on I 8335 539 9 got Ekm rum 95 ark an ya 51 1 2 Has 93166 ngoxoi 0st 93 xolfosf got 2rd 25 L1 x Y 95 9 in we 92 9 f313 72 9 3 0 532 61534 9 8amp7quot can 9 22 32 Wan Eff fofrovmu box sh 653 936 eat at as GE 0 HIHOI nup A w 3 IO mia nuox apvfstsu git mstaunnf 7 pa h 2 8a w a 5 iii 13 rail o 25 a 72 as 31 9cit have 9 Q nes rr oh g ip T 53 9 sol 183 is I P quot33quot curse no 6 0 PW 0 290 ARV a if wt tbm WI PW hut m 9399 cft TMch quot20kt 11amquot The WW 0 we Rm o M t v an OWNact39va at n tints i5 och E39BZL ASSN e u a Ioviu39dnl he wick mm Au t wa39h a A a ham calJ c WOW we Gunw 0 p Lukas a n a i t c m lqr Eda60 Oh 0 KinHM M 55 W 0 lAc M 30 h4 4 Lgi 4 9H I m uku n H v akHugs I tdf td h HIVK e o v 4S MROh Poi Q to u at new a L can t in u amp 3 2 a A Luca to 304 p LN 0 Anzac46 WIN 0 Odd S39h lQy vw w gt Box 03 ab 44 saw my I M h k No on new 9 Region 392 is Io f aquot M l kid a Ha on we a w v n ach caucm M M C 39 m Thanh1 Aquot rhymest of v 18 u 14 Plane 1 Qt an HCHKOW39II AQMMH 1 14 0039quot FM a 912 PM Me M Me WI mmq is sq3 00quot 4 u 3 Voronoi Diagrams o A set P 2 191192 pn of n points called sites 0 Suppose each point of the plane is attracted to the site closest to it o This induces a partition of the plane each site owns the part attracted to it o What does this partition look like This is called the Voronoi Diagram of P Subhash Suri U C Santa Barbara Applications o Voronoi diagram is a promixity diagram Think of the post of ce analogy 0 Many applications are proximity driven location of retail stores emergency services facilities etc 0 Strategy questions like Where to locate a new store 0 In science forces are inversely proportional to distances 0 Phenomena like crystal growth cluster formation give rise to Voronoi diagrams Subhash Suri U C Santa Barbara Preliminaries 0 Begin with the simplest possible setting two sites p and q o What does their Veronoi diagram look like V0rp V0rq o What happens with three sites pq39r Subhash Suri U C Santa Barbara A Veronoi Cell o Generalizing we realize that a Voronoi cell is the intersection of n 1 halfplanes 399 a a Each halfplane de ned by the bisector line 0f Pair 197197 hpp7 2 3939 dista p g di8tcvp7 o Bisectors are the building blocks of the Voronoi diagram Subhash Suri U C Santa Barbara Voronoi Properties o A site s Voronoi cell Vp is a convex polygon o Vp has at most n 1 sides a For every point a in the interior of Vp the closest site of QC is p 0 Every point a on the boundary of Vp is equidistant from at least two sites one of which is p o The Voronoi Diagram VP is the union of voronoi cells of all sites in P Subhash Suri U C Santa Barbara Properties o How do various cells interrelate 0 int Vp 0 int Vq I 0 interior of the cell belongs to exactly one site 0 The union of all cells covers the plane each point a must have some closest site 0 Thus VP is a planar subdivision of R2 Subhash Suri U C Santa Barbara General Position o The degree of a vertex v in VP is the number of edges incident to v o The degree also equals the number of cells that have 1 on their boundary 0 If 1691 2 k then k sites are equidistant from v o The equidistant sites are cocircular c We make the general position assumption that no more than 3 sites lie on a circle so all vertices of VP have degree three Subhash Suri U C Santa Barbara Boundedness o A cell Vp is unbounded if and only if p is on the convex hull of the sites a If p on CHP consider ray normal to the support line of p o All a on this ray have p as their nearest site Thus Vp is unbounded ray o If p 93 CHP then p lies inside sorne triangle Aabc Where a b c on the hull c Any point suf cient far out has a b or c as their closest site not p 0 So Vp must be bounded Subhash Suri U C Santa Barbara Properties o v is a Voronoi vertex iff it is the center of an empty circle that passes through 3 sites 0 If v is center of such a circle it must be that v E Va Vb Vc and so it s a Voronoi vertex 0 If v is a Voronoi vertex let 1 I Va Vb Vc No other site can be closer to 1 than a b c and so the circle with center 1 and radius va is empty Subhash Suri U C Santa Barbara Interprocedural Control Flow Analysis Using Constraint based Approach C56463 The Dynamic Dispatch Problem n Which function is called by pX int myFunc int pint return px I P is a function pointer What function could p point to what is the value of p I P is a function parameter so the value of p is unknown unless interprocedural dataflow analysis is performed in But interprocedural dataflow requires an interprocedural control flow graph or a call graph I The problem is relevant for I Imperative languages that allow functions as parameters I Object oriented languages and functional languages c56463 Interprocedural Control flow Analysis El Example code int f int xint return x1 int 9 int y return y 2 int n int 2 return 2 3 int main return fg fh n For each function call what functions may beinvoked c56463 Defining the Analysis El What is the domain of analysis I What is the solution space i What could be the values for each function pointer expression El Specification of the analysis I How to compute the solution El how to accommodate the information flow from function definitions to function invocations El Welldefinedness of the analysis I What are the properties of the solution space I Does it compute a solution I Does the algorithm terminate I Is the solution precise c56463 Specification of Domain i What is the solution For each expression in the program could it have a function pointer value If yes what functions may it point to if no the solution is Q I Must keep track of the values of variables especially function parameters El To represent the solution label each expression within the program compute An abstract cache C so that for each expression e E1 Ce contains the set of function values e may have I An abstract environment P so that for each variable x n Px contains the set of function values x may have c56463 ThelnputLanguage n Assume a small functional language e c constant values I x variable reference I fun f x gt e0 function with name f parameter x and body 30 l e1 e2 invoking function e1 with argument e2 I if e0 then e1 else e2 if e0 is true return e1 else return e2 I let x e1 in e2 introduce local variable xe1 in e2 El Why functional language I Functions are firstclass objects allow nested functionsscopes 1 Can be used to model virtual functions in objectoriented programming I Dataflow is explicit a single symbolic value for each variable No variable is ever modified a For imperative programming languages perform global dataflow analysis build SSA c56463 Example Code and Controlflow Analysis Solution n Example code fun f x gt x fun g y gt y I Labels 1 x 2 fun f x gt x 31 y 4 fun g y gt y 5 fun f x gt x fun g y gt y u Example CFA solution guesses of the GP mappings fun g y gt y fun fx gt x o fun g y gt y fun g y gt y fun g y gt y o fun fx gt x L LQ ltgtltU lIgtCOI fun g y gt y c56463 Solution Space of CFA El Formally I Abstract values Val PowerTerm 1 Each term is a function definition in the form fun f x gt e0 I Abstract environment Env Var gt Val 1 Var the set of all variables including function parameters I Abstract cache Cache 2 Label gt Val 1 Label the set of labels expressions El Each solution a pair of PC QEnv Cache c56463 Specification of CFA i What properties must be satisfied by PC to be a correctacceptable solution I CP l e means that CP is an acceptable Control Flow Analysis Solution for the expression e 1 GP I C Arbitrary solutions are acceptable for a constant value c 1 GP l x iff PX Q C The solution for an variable must be a subset of the solution for its label each variable has a single value through each of its lifetime 1 OP l fun f x gt e001 iff CP l eO0 and fun f x gt e0 Q C1 and fun f x gt e0 Q Pf The solution for a function definitionabstraction label must include the function definitionabstraction c56463 Specification of CFA 2 Function invocation application I CP I e11 e223 iff CP I e11 CP I e22 and V fun f x gt e0o E C1 CPI e00 C2 Q Px and Co Q C2 n The solution for function parameter x must contain that of the invocation argument e2 n The solution of the function invocation must contain that of the function body a Local variables nested scopes I CP I let X e11 in e223 iff CP e11 CP 22 C g Px and Cz g C3 u The solution for the local variable x must contain that of its defined value a The solution of the outer scope must contain that of the inner scope Conditionals l CP I if e00 then e11 else e223 iff CP e00 CP e11 CP e22 and C2 g C3 and Cz g C3 n The solution of the outer scope must contain that of the inner scopes both branches AA C56463 10 Example Code and Controlflow Analysis Solution El Example code fun f x gt x fun g y gt y I Labels 1 x 2 fun f x gt x 31y 4 fun g y gt y 5 fun f x gt x fun g y gt y El Example CFA solution guesses of the CP mappings Are the valid CP C P 1 fun g y gt 3 fun g y gt y 2 fun fx gt x fun fx gt x CP I fun f x gt x fun g y gt y 3 Q Q C P E fun f x gt x fun g y gt y 4 fun g y gt 3 fun g y gt y 5 fun g y gt y fun g y gt y X fun g y gt y Q y Q Q f funfxgt x funfxgt x 9 fun g y gt y fun g y gt y c56463 11 Welldefinedness of CFA Analysis II Difficulty Cannot build CP I e by structural induction on the expression e I Eg function invocation application CP I e11 e223 iff CP I e11 CP I e22 and V fun f x gt e00 E C1 CP e00 C2 Q Px and Co Q C2 I There is no guarantee that Cfo has been computed correctly before computing Cf2 II Coinductive definition the solution space includes all guesses of CP that satisfy the specifications I Must apply all constraints to iteratively modify the solutions until they become correct I The best solution is the smallest one that satisfies all the constraints C56463 12 Correctness of Specification El If there is a possible evaluation of the program such that the function at a call point evaluates to some function definition I then this definition has to be in the set of possible definitions computed by the analysis I Existence of solutions I Every expression accepts a least CFA solution C56463 13 Constraint based Analysis El Syntaxdirected analysis I Reformulate the analysis specification 1 Construct a finite set of constraints based on structural induction I Compute the least solution of the set of constraints El Each constraint has the form sol1 g sol2 or t E sol or t E sol1 gt sol2 g sol3 I where a Each sol is either C or Px f is label x is a variable 1 Each t is either fn x gt e0 or fun f x gt e0 C56463 14 Constraintbased Analysis n For each expression e compute Conde I Condo constants Condx Px g C l Condfun f x gt e0 CondeO U fun f xgteOQ CD U fun f x gt e0 Q Pf function clef I Conde11 e223 Condel U Conde2 U t E C1 gtC2 Q Px V t fun f x gt e00 U t E C1 gt C0 Q C3 V t fun f x gt e00 I Condlet x e11 in e223 Condel U Conde2 UC1 Q Px U Cz Q C3 I Cond if e00 then e11 else e223 CondeO U Condel U Conde2 U C2 Q C3 U Cz Q C3 variables c56463 Example Constraint Construction Condfun f x gt x12 fun g y gt y34 5 fun f x gt x Q C2 fun f x gt x Q Pf Px Q C1 fun g y gt yQC4 fun g y gt yQPg Py Q 03 fun f x gt x Q C2 gt C4 Q Px fun f x gt x Q C2 gt C1 Q C5 fun g y gt 339 Q 02 gt 04 Q Py fun g y gt y E 02 gt 03 Q 05 cccc 63 Solving the constraints El Input a set of constraints for the entire program Output the least solution CP to the constraints Idea equivalent to finding the least fixed point of a monotone function defined by the constraints I Straightforward iterative algorithm has n 5 cost where n is the size of the program expression I A more sophisticated algorithm takes nA3 complexity Ell El The graph based algorithm I Build a graph where a Each node n corresponds to a unique C or Px gtvaln a Add an edge from node n1 to n2 if any change to valn1 may require modifications to valn2 I Use a worklist to keep track of nodes to change C56463 17 Constraint Solving Algorithm 1 El Define addt p if t i p p p U t appendpworklist I Step 1 Initialization I worklist nil I for each label or variable x do n ValCl nil EdgeCl nil or ValPx nil EdgePx nil I Step 2 Building the graph I for each co in Condprogram do case cc of t Q p addtValp p1 Q p2 appendcc Edgep1 t Q p gt p1 Q p2 appendccEdgep1 appendCCEdgep 7 5 39 P F X V PU Pg C56463 18 Constraint Solving Algorithm2 I Step 3 Iteration I while worklist is not empty do q RemovefirstW for each co in Edgeq do case cc of p1 Q p2 addp2 Valp1 t Q p gt p1 Q p2 if t Q Vap then addvalp1 p2 Val Iteration O Propogate C2 Propoage Px Propoage C1 01 Q Q fun g y gt y fun g y gt y C2 fun f x gt x fun f x gt x fun f x gt x fun f x gt x 03 Q Q Q Q 04 fun g y gt y fun g y gt y fun g y gt y fun g y gt y C5 Q Q Q fun g y gt y PX Q fun g y gt y fun g y gt y fun g y gt y Py Q Q Q Q Pf fun f x gt x fun f x gt x fun f x gt x fun f x gt x Pg fun g y gt y fun g y gt y fun g y gt y fun g y gt y c56463