Advanced Topics in Computer Graphics
Advanced Topics in Computer Graphics CMPS 290
Popular in Course
Popular in ComputerScienence
This 133 page Class Notes was uploaded by Dr. Elyssa Ratke on Monday September 7, 2015. The Class Notes belongs to CMPS 290 at University of California - Santa Cruz taught by Staff in Fall. Since its upload, it has received 27 views. For similar materials see /class/182267/cmps-290-university-of-california-santa-cruz in ComputerScienence at University of California - Santa Cruz.
Reviews for Advanced Topics in Computer Graphics
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 09/07/15
mm13 n N IVAum 391 gtMANMIHH EENFNE hvll I c Lauri NEEDED Flk LVFF mm a Eevunrnwur In 9 anquot gt nucmsumwb MATH E ww m Awrmm MMMIM lH HT L 9 125504 A2 bMVL menu we PVLJtllilEV IF 116075 W9 47 l 46qu Mp HLL Am 76 mm runin 7 MMMM Mun mar HW0 MlARTLHQE I MM7 l39 Mum3950 mme waneucn LAN 15 uka rm BENEFIT 0F nunAMI Cumin M21550 M R IVEHm ARE WE PLANut Mo How 75 Mm MIMIMUN duow zcu curaux w usarm rwuwmue FOR LDUG TIME CAML 15130 was Abc39Hnn E 0EAllrj V mass A 39v HA III 70 Ar PREPARED 1U anFEEEIIT EV WRFIV usVT a CF Hasmas m gaunst Two WW 11M FIIL39DHt MMIIIl r ArmyLn jfm39uu up 59mm 3415 X 71 sum llLOPLA J VA QEerLum 17H swig V Mr me Hi 4M PriEll MM 1M4 EelJ55 4 m 1 r N G 20 n LnIv 4 37 39UI rsues M p w 4 39ItTHrLDES 0F Ilia Ems MWum L Mac s limo FLL u MW Mfgmun gtw I9 My BAsl 7HE Hi THE mmy ME AN 125va TM mimicUL metro F U3 nVw my IWT WVmum Fm bk Nl ri l I39m39 MAW M 14 An TugIssuer mm M ammu rAlsercu mm M A 4115415 1an n we as mumsm Fm Mun 0511 EK NUPUE M sELFCH U A lL HH cumIVES inletHIE w A TRALMHN vETSLAV7A7IED THEN N0 REPMuuanxquot AM Mild LwnMA Nil NW fir alwk mku or L jflEUT MURbe TWAAnon TRAILMSL N Mmr Hum9 L77 TEAMAlum TIM ur pm rg w Ianvmm pm EL W EIPTWN 1N7 UTHL LEAH me nsmu 5Lrnurwu 45454 VI7H Was97 A was 25 NWJgtIE5 NVTIIQL IF MESETIM NOT DIE kitJUN vac THEv FHAnaAAu T w SEEMSMAT memm 197 EPAEC F l F ALL ANlElWWT AL H L 7 P 736 1 lWDlLy39Eu E 42M HAL 6M5 FIML ELMAIME oi 3936 L 39t kEVERSE TeMLZRHUWM PLIE LNML Art0Lme LF VamA rmwr DkJ EIEN MHDMMM HLE LwnATr UI LIFlsg 21mm Wm M we run an mmm mmm REALM MENTE39 LEL Us STANDWPB ANNIFN TWETHER 0quot WMMLLEL RMIUN HMHIIJT a CTANMRD 2 P n7 FkEGllElI r r msz T 5m N quot W EWM Mum a mass Mm Qunn ta vn RT PCR Cnmhm mgelkNAnnd aninzcancenmlmns g m A nudud my YmL mpmu mm m mm i CKJ Pmymm Tndmum umm Dwmmm 5 45mm quotmum nuk n mmmn an momma mummy I VEke 5 mm IM Cm 55 MA Orvnszmg r w AHPLFmA39H M r plum K Mersey TI mmnrr mm gym N u agmm UNIu spam 0 Mg tuxmm LUNA mm x Erpuaucy EFFVUEIL U1 Mu rLuLVMV FitU 5 5 I nALETEF many UMP3561615 lam MINI27 MINm DF TIEGET ANA AF WER m m tLE Br NALAMIIWT 0F 39MQCET AAl F E j7LIE 5 MIA I39DMB F1312 PM if F 7 I4E QTM LARD M pg u Ea DESIGN swammo so THH W W IIWU n mum PJV EUEAUEIM RT 3 HIE SAIW Eng MEL 70 intU TAMET cw m5 p N mad 5an a Eumpmlwg muunr rmca 33H L 7 anvil 30quot a Ts ALTERNATE Hymn eiAvoAzn sEpEemEL I Illom bibPEDIouE Convex Optimization 7 Boyd amp Vandenberghe 4 Convex optimization problems 0 optimization problem in standard form 0 convex optimization problems 0 quasiconvex optimization 0 linear optimization 0 quadratic optimization 0 geometric programming 0 generalized inequality constraints 0 semidefinite programming 0 vector optimization L1 Optimization problem in standard form minimize f0 subject to g 0 i1m hi ac0 i1p o 35 E R is the optimization variable 0 f0 Rquot a R is the objective or cost function 0 fi R a R i1m are the inequality constraint functions 0 hi R a R are the equality constraint functions optimal value l S 07 7 17quot397m7 7 17quot397p o p 00 if problem is infeasible no 35 satisfies the constraints 0 p 700 if problem is unbounded below H Convex Optl mization problems Optimal and locally optimal points 35 is feasible if 35 E dom f0 and it satisfies the constraints a feasible 35 is optimal if f0 11 Xopt is the set of optimal points 35 is locally optimal if there is an R gt 0 such that w is optimal for minimize over 2 f0z subject to g0 i1m 0 i1p HZ i2 S R examples with n 1 m p 0 0 f0 35 3 7 335 p foo local optimum at 35 1 Convex optimization problems 44 Implicit constraints the standard form optimization problem has an implicit constraint in P JCED domfi m domhi 10 i1 c we call D the domain of the problem 0 the constraints g 0 0 are the explicit constraints 0 a problem is unconstrained if it has no explicit constraints in p 0 example minimize f0 7 221 10gbi i aiTgc is an unconstrained problem with implicit constraints aiTw lt bi Convex optimization problems 4 4 Feasibility problem find 36 subject to g 0 z 1 m 07 17 7p can be considered a special case of the general problem with f0 0 minimize 0 subject to 0 i1m hi 07 17 7p 0 p 0 if constraints are feasible any feasible 35 is optimal o p 00 if constraints are infeasible Convex optimization problems 5 Convex optimization problem standard form convex optimization problem minimize f0 subject to g 0 i1m T 7 aimibi 271p 0 f0 f1 fm are convex equality constraints are affine 0 problem is quasiconvex if f0 is quasiconvex and f1 fm convex often written as minimize f0 subject to fi g 0 i1m ac b important property feasible set of a convex optimization problem is convex Convex optimization problems 4 6 example minimize f0 35 35 subject to f111 S0 h1 1 22 0 0 f0 is convex feasible set 351 2 351 7352 g 0 is convex c not a convex problem according to our definition fl is not convex hl is not affine 0 equivalent but not identical to the convex problem minimize 35 35 subject to 351 g 0 1 2 0 Convex optimization problems 7 Local and global optima any locally optimal point of a convex problem is globally optimal proof suppose 35 is locally optimal and y is optimal with foy lt f0 35 locally optimal means there is an R gt 0 such that z feasible i l2 S R gt f0Z Z f0 consider 2 0y 17 0 with 0 RQlly o llyiml2gtR soOlt0lt 12 c z is a convex combination of two feasible points hence also feasible 0 i l2 R2 and foz S 9fo1 9foy lt fo which contradicts our assumption that 35 is locally optimal Convex optimization problems Optimality criterion for differentiable f0 35 is optimal if and only if it is feasible and Vf0Ty i 35 Z 0 for all feasible y if nonzero Vf0 defines a supporting hyperplane to feasible set X at 35 Convex optimization probiems 4 9 0 unconstrained problem 35 is optimal if and only if 6 domfo 0 o equality constrained problem minimize f0 subject to Aw b 35 is optimal if and only if there exists a 1 such that wedomfo Ab Vf0AT10 o minimization over nonnegative orthant minimize f0 subject to w 5 0 35 is optimal if and only if wedomfo 50 Vf0i0 igt0 Convex optimization probiems 10 Equivalent convex problems two problems are informally equivalent if the solution of one is readily obtained from the solution of the other and vice versa some common transformations that preserve convexity o eliminating equality constraints minimize f0 subject to f 35 g 0 i Am b 1 m is equivalent to minimize over 2 f0Fz 0 subject to fFz 350 g 0 i 1 where F and 350 are such that 4353 ltgt Fz0forsomez Convex optimization problems 0 introducing equality constraints minimize f0Ao be subject to fiA b S 0 i 1 is eq uivalent to m minimize over 35 y f0y0 subject to fy g 0 i 1 m i01 m o introducing slack variables for linear inequalities minimize f0 subject to aiTgc g b i1m is eq uivalent to minimize over 35 s f0 subject to aiTsb i1m 820 i1m Convex optimization problems o epigraph form standard form convex problem is equivalent to minimize over 35 t t subject to f0 i o minimizing over some variables minimize f012 subject to fi1 0 i 1 m is eq uivalent to minimize f01 subject to fi1 0 i 1 m where fo1 1IlfI2 f01 2 Convex optimization problems 13 Quasiconvex optimization minimize f0 subject to g 0 i 1 m Am b with f0 R a R quasiconveX f1 fm convex can have locally optimal points that are not globally optimal my few L14 Convex optimization problems convex representation of sublevel sets of f0 if f0 is quasiconvex there exists a family of functions g3 such that o t is convex in 35 for fixed it o t sublevel set of f0 is 0 sublevel set of t 216 f0 S t ltgt M36 S 0 example with p convex q concave and p Z 0 q gt 0 on dom f0 can take t p i tq o for t Z 0 Z convex in w o g t if and only if t g 0 Convex optimization problems 15 quasiconvex optimization via convex feasibility problems 0 for fixed it a convex feasibility problem in 35 o if feasible we can conclude that t Z 11 if infeasible t g p Bisection method for quasiconvex optimization given l S p u 2 p tolerance e gt 0 repeat 1 t l u2 2 Solve the convex feasibility problem 3 if 1 is feasible u 15 else l 15 until u l S e requires exactly 10g2u 7 06 iterations where u l are initial values Convex optimization problems 16 Linear program LP minimize cTw d subject to Gas 5 h Am b o convex problem with affine objective and constraint functions 0 feasible set is a polyhedron Convex Optlleathn problems 17 Examples diet problem choose quantities 1 Jan of n foods 0 one unit of food j costs cj contains amount aij of nutrient i 0 healthy diet requires nutrient i in quantity at least bl to find cheapest healthy diet minimize cTw subject to Am 5 b 35 5 0 piecewiselinear minimization mInImIze maxi177mai 35 bi equivalent to an LP minimize it subject to aiTbi gt i1m Convex Optlleathn problems 18 Chebyshev center of a polyhedron Chebyshev center of Pa bi i1m is center of largest inscribed ball 6 mu llullz r o aiTgc g bi for all 35 E B if and only if T lt T lt b Supai in u llullz 7 7quot a1 36c 7quotllazllz 7 l 0 hence 35C 7quot can be determined by solving the LP maximize 7quot subject to aiTwc rlail2 g bi i1m Convex optimization problems Generalized linear fractional program minimize f0 subject to Gas 5 h Am b linearfractional program T d few dom few m 6ng f gt 0 o a quasiconvex optimization problem can be solved by bisection 0 also equivalent to the LP variables y z minimize cTy dz subject to Gy j hz Ay bz eTy fz 1 z Z 0 Convex optimization problems generalized linearfractional program CZTJJ di igllymyr 631 fia domf0 7 l gt 0717 77 M36 a quasiconvex optimization problem can be solved by bisection example Von Neumann model of a growing economy maximize over 35 35 mini177nji subject to 35 5 0 375 5 Am 0 E R activity levels of n sectors in current and next period 0 375 produced resp consumed amounts of good i o growth rate of sector i allocate activity to maximize growth rate of slowest growing sector Convex optimization problems 21 Quadratic program QP minimize 12TP qu 7quot subject to Gas 5 h Am b o P E 5 so objective is convex quadratic o minimize a convex quadratic function over a polyhedron Convex optimization problems 22 Examples leastsquares minimize Am i o analytical solution 35 Alb AJr is pseudo inverse 0 can add linear constraints e g l j 35 j u linear program with random cost minimize cTw waTZJC EcTw yvarcT subject to Gas 5 h Aw b o c is random vector with mean 5 and covariance Z T T 0 hence c 35 is random variable with mean 5 35 and variance JCTZJC o 39y gt 0 is risk aversion parameter controls the trade off between expected cost and variance risk Convex optimization problems 23 Quadratically constrained quadratic program QCQP minimize 12TP0 quw To subject to 12TPiqZTri g0 i1m Am b 0 Pi E Squot objective and constraints are conveX quadratic o if P1 Pm 6 51 feasible region is intersection of m ellipsoids and an affine set Convex optimization problems 24 Second order cone programming minimize ngc subject to bil2 g ciTac di i 1 m Fm 9 1416 Rnixn F 6 RPM 0 inequalities are called second order cone SOC constraints Aim b ciTw d E second order cone in Rm 0 for n 0 reduces to an LP if c 0 reduces to a QCQP o more general than QCQP and LP Convex Optl mlzatlon problems Robust linear programming the parameters in optimization problems are often uncertain 69 in an LP minimize cTw subject to aiTgc g b i 1 m there can be uncertainty in c ai b two common approaches to handling uncertainty in a for simplicity o deterministic model constraints must hold for all a E 5 T minimize c 35 subject to aiTgc g b for all a E 5i i 1 m o stochastic model a is random variable constraints must hold with probability 1 minimize cTw subject to probaiT g b 2 n i 1 m Convex Optl mlzatlon problems deterministic approach via SOCP 0 choose an ellipsoid as 51 51 ELZ39 Piu g 1 cil E R Pl 6 RMquot center is 61139 semi axes determined by singular valuesvectors of Pl 0 robust LP minimize cTw subject to aiTw g bi Vai E 5i i1m is equivalent to the SOCP minimize cTw subject to ELIT35 g bi i1m follows from supHuHQS ELi PiuT EriTgc Convex optimization problems 27 stochastic approach via SOCP o assume ai is Gaussian with mean 61139 covariance ZZ ai NELZ T i T i 7 T probaiT g bi gt W llzi ll2 o a w is Gaussian rv with mean EL 35 variance wTZZw hence where lt1gt 1mffooe t22 dt is CDF ofAo 1 o robust LP minimize cTw subject to probaiT g bi Z n i1m with n 2 12 is equivalent to the SOCP minimize cTw subject to ELIT35 gt 1nl232l2 g bi i1m Convex optimization problems 28 Geometric programming monomial function ag CT12quot domf R1L with c gt 0 exponent 041 can be any real number posynomial function sum of monomials K chmilkmggk 36 domf R1 k1 geometric program GP minimize f0 subject to g 1 i1m 1 i1p with fl posynomial hi monomial Convex Optl mlzatlon problems Geometric program in convex form change variables to yi 10g 351 and take logarithm of cost constraints 0 monomial ag 035i 35quot transforms to 10gfeyleyquotaTyb b10gc o posynomial ag 251 ckwilkwggk aim transforms to K T 10gfeyl eyquot 10g 2 eakyH k bk 10g ck k1 o geometric program transforms to convex problem minimize 10g Ef exmaOTkerbOk subject to log 251 expai7y g 0 i Gy d 0 Convex Optl mlzatlon problems Design of cantilever beam segment 4 segment 3 segment 2 segment 1 y W F o N segments with unit lengths rectangular cross sections of size wi gtlt hi 0 given vertical force F applied at the right end design problem minimize total weight subject to upper amp lower bounds on w hi upper bound amp lower bounds on aspect ratios hiwi upper bound on stress in each segment upper bound on vertical deflection at the end of the beam variables wi hi for i 1 N Convex optimization problems objective and constraint functions 0 total weight wlhl thN is posynomial aspect ratio hiwi and inverse aspect ratio wihi are monomials maximum stress in segment i is given by 6iFwih12 a monomial the vertical deflection yi and slope vi of central axis at the right end of segment i are defined recursively as Ui 12i 7 12 F Ewihg 39Ui1 yi 62 713 F Ewhg vi1 yi1 for i NN71 1 with UN1 yN1 0 E is Young39s modulus vi and yi are posynomial functions ofw h Convex optimization problems formulation as a GP minimize wlhl thN SUbjeCt to wmixwi S L wminw1 S 1 i1 N hmzlalxh i S 1 hminh1 S1 i1N Smixwiilhi S 1 Sminwihiil S1 i1 N 6iFaglixwi 1hi 2 g 1 i 1 N ynjixm 1 note we write wmin S wi S wmax and hq nin S S hmax wminwi S 1 wiwmax S 1 hminhi S 1 hihmax lt 1 c we write 5min g hiw lt Smax as Sminwihi S 1 hiwismax lt 1 Convex optimization problems 33 Minimizing spectral radius of nonnegative matrix PerronFrobenius eigenvalue ApfA 0 exists for elementwise positive A E Rnxn o a real positive eigenvalue of A equal to spectral radius max 0 determines asymptotic growth decay rate of Ak Ak m Agf as k a 00 0 alternative characterization ApfA inf Av j v for some 1 gt 0 minimizing spectral radius of matrix of posynomials o minimize ApfA where the elements ALI are posynomials of 35 0 equivalent geometric program minimize subject to 21Aijvjvi g 1 i 1 n variables A v 35 Convex optimization problems 34 Generalized inequality constraints convex problem with generalized inequality constraints minimize f0 subject to jKi 0 i1m Am b 0 f0 Rquot a R convex fl Rquot a Rki Ki convex wrt proper cone Ki 0 same properties as standard convex problem convex feasible set local optimum is global etc conic form problem special case with affine objective and constraints minimize cTw subject to F35 9 5K 0 Am b extends linear programming K RT to nonpolyhedral cones Convex optlmlzatlon problems 35 Semidefinite program SDP minimize cTw subject to 1F1 2F2 nFn G j 0 Am b with G e sk o inequality constraint is called linear matrix inequality LMI 0 includes problems with multiple LMI constraints for example 1F1npn jQ x1F1nFn jO is equivalent to single LMI F1 0 F2 0 F 0 C 0 40 lo Flj zlo F2 Mlo Fnl0 G Convex optlmlzatlon problems 36 LP and SOCP as SDP LP and equivalent SDP LP minimize cTw SDP minimize cTw subject to Am 5 b subject to diagA i b j 0 note different interpretation of generalized inequality 5 SOCP and equivalent SDP SOCP minimize ngc subject to billz S ciTw di i1m SDP minimize ngc T 39 Cidl1 A1bl c0 i1m subject to AibiT CiTdi i Convex Optl m ization problems Eigenvalue minimization minimize AmaXA where 14135 A0 1141 wnAn with given AZ 6 sh equivalent SDP minimize it subject to A j t 0 variables 35 E Rquot t E R 0 follows from Amaxm g t ltgt A j t Convex Optl mization problems Matrix norm minimization minimize AmaxATA12 where 14135 A0 1141 wnAn with given AZ 6 prq equivalent SDP minimize it subject to 7 ALT gt 0 0 variables 35 E R t E R o constraint follows from llAllz t ltgt ATAjtZI 720 t A E y l AT 2 l i 0 Convex Optlleathn problems 39 Vector optimization general vector optimization problem minimize wrt K f0 subject to g 0 z 1 m Z 17quot 7p vector objective f0 R a Rq minimized wrt proper cone K E R4 convex vector optimization problem minimize wrt K f0 subjectto figs g0 i1m Am b with f0 K convex f1 fm convex Convex Optlleathn problems 40 Optimal and Pareto optimal points set of achievable objective values 0 f0 as feasible 0 feasible 35 is optimal if f0 is a minimum value of O o feasible w is Pareto optimal if f0 is a minimal value of O O O fowl fox 30 IS optimal gap is Pareto optimal Convex optimization problems 41 Multicriterion optimization vector optimization problem with K R1 fo F1ltwFqltw o q different objectives Fi roughly speaking we want all Fi39s to be small 0 feasible 35 is optimal if y feaSible gt fob 5 f0y if there exists an optimal point the objectives are noncompeting o feasible mp0 is Pareto optimal if y feaSible f0y j f0po f0po f0y if there are multiple Pareto optimal values there is a trade off between the objectives Convex optimization problems 42 Regularized least squares multicriterion problem with two objectives F106 llAw 7 bllia F206 llwllg 0 example with A E R100x10 10 o shaded region is O T 0 heavy line is formed by Pareto if 5 optimal points 5 10 2 F106 lle bllg Convex optimization problems Risk return trade off in portfolio optimization minimize wrt REL i varTZm subject to 1T3 1 35 5 0 o 35 E Rquot is investment portfolio 35 is fraction invested in asset i o p E R is vector of relative asset price changes modeled as a random variable with mean 15 covariance E o STJC E7quot is eXpected return JCTZJC varr is return variance example 4 we we 10 961 mean return allocation x 0 10 20 0 10 20 standard deviation of return standard deviation of return Convex optimization problems 44 Scalarization to find Pareto optimal points choose gtK 0 and solve scalar problem minimize Tf0 subject to 0 i1m h0 i1p if 35 is optimal for scalar problem then it is Pareto optimal for vector optimization problem for convex vector optimization problems can find almost all Pareto optimal points by varying gtK 0 Convex optimization problems 45 examples 0 for multicriterion problem find Pareto optimal points by minimizing positive weighted sum ATf0 1F1 qu o regularized least squares of page 4 43 with 1 7 minimize Am i for fixed 7 gt 0 a least squares problem 0 risk return trade off of page 4 44 with 1 7 minimize i Tw waTZJC subject to 1T3 1 35 5 0 for fixed 7 gt 0 a QP Convex optimization problems 46 quot LQEJLj ixiyg 3 i CUT201M i I 1 A x r m 1 A quot77 m p 1 llquot4150 Os pram95 cg IN I39MW39L W C F39xewex mm 11 L m N m cm 23sz 232 57 WUIL 119MHz Ifm SQ39H af 1 1 CL N NV my AA 7ih N l A w 1 NH on AC x i f U 5 E is I 5 5 LEARUM a LU LINEN2 T flrIPEQAIrLw FolUOWGVg lt ON CHAMUEL XUAMR39 LO 2 SYMBOL lt gtg 103Pxi l XI 2 J 1 X f Bra quot2 V3 2 X t 39i y u 5 Asaea M Cu 2 p It Is I m l 39 O m gem919G N 109 O t X INFINITE 139 L 8th vc 03 l Emraom gageAU EXPgCiuw SLUEPE ICLE H X 1 i Z py 052 7x 2 7 DIM I p low 39 lam long 13 H u HTMMU C0 gt E I xx 12 Low J 3 v m X7 I R PLCQ 0lvll LI0 X g 0 i COMMOE mm M270 ONE 2 J M1 l Q 9qu THEN PROBQ 000 H E w 39139 m r3 r a x PECFE b OIOELEU a TM X X L 1 X L m 24 E 00 MM 8a 0913 15 8175 Wmwa commacm H1 2 1 S 1 MM 13175 Q 0mm A9IGAJG smut5019 A BramNa COMMMM w AW sEid wmACE or cmewwws W157 115 WQow jm DENMBAE C 392 4 Xr 4 EXPECTEU U r 1 PM C A COIOIEUEAJ TM com 7 LENGTH 01 Cong 4021 FOR x OPTIMAL My 04 MIAHme L C THM X L gt e NZX5w quotWL NW1 TM a 01515 ARE p 2 irzquot m L MOEG N O Smear FltF CHAPTER 0f 00 tEe Z THOMA Pi PWO f R E Lmt UL EIU TRON PROBAng39r lI3 i 069 A 51 37 f 9mm new role I5 l UEvthZAJccgg mmm 40 Ar VI APer more 1W3 30 W A 73 0H VVZ Camwag 05 gMPLEX L H 3 MJNw mqu I Q 5 Z 9 Lu EXPECTED CODELEAJQTH Eypgcmb COM My W 0F BEST CODEBOOK Of ZEQT p006 Book We FOR 7 EXPEH39AToUS qeg Wm x Z A 1 WM P39 L 11 LZPM Pl ipt m39u mm mp 20 NOT T00 S TEEP AT RoombAe r MRR39EW VEQW QTEEV XOR CHMALFX DUAL ME M RELmug Emmaw T A REOlLAIZlZEEC W MOTIVATION 0 MAszin A E M iVIEA MQE39OF pew25399 W AAALJKCQ STREAl MlKlzil39 5mm OF WPEK T 20139va Cm I NolaMum WISMITVMTOB Fm Jaw To T M 110091 EXPfiIETL WITH PROBABILIW Wm GE LOIS JG70 It 01le I 2 meme Logs JUL we EXNCYED LOQL but Lt VILLA wv I i 2t DOT L059 GALZ lonumuom 01quot MDTE I M N bUu 2 MA lt AUN I d1 4 Lu L6 7 ummw Zwi 39 RELA ruI Eurrow we IN LA ST wgqem ULELTOR m LA 9 wanewuurmz Te IAL lvllAutulgwo Copy3x yMUOTON QO3 OET To LINEM COUQTQUMT COMSTEAUT W L RUM Z w M 41 WILL 4 gt 3 mm 4L LA RAUQIAAJ Mmewow Mu L7IPLVGQ FIND owlML gammav 8 QEI THUG ALL chl lVATHl 0E L 70 ZERO 92 iwwl so m OUH E ChugryaHNT 9L W I V aWi w39 ld J J 4 Lt Jr 770 m jmmc LtL A Ltlgt gt 2 but h Q W 239 ENMRCE 39 gt W1 Q MLt39b L FINN New I Wu I i 2 WTWrm w L tf 13911 1 M b emu mm 7quot Am is WM a M tag Alsoi WM 1 Mg Alw 11 W LEE 3 Lw macmug wammx I w A 7 7 W v WhitC Ex COi quot ML 1 7 L U K JEN U 39 Lu I l l 8 I L Lu 1 Z Li 39 WM 39 734 4 L I L39tl An 24 l v 1 1 V r w Q N a M Lt Lu ML L by w 4 7 16 6 o r I quotW i gt 9quot I 4 114 Mm 4 l It 1 2 WM l MLSquot ML5RLECOMEA MXL gt M 4 a 39Et 1 quot Z Wt l quot 9 LI i M W V iiiLL 1 gtva L1 1quot pva L096 0139 1099 0F coM PA RATOR A My 2 AU 63 A M7m s I Z A 7 7t AWNH TELEQCOPWG tn T W W N i V MILL hem Z Wt39Lv 4 1 a V I M T W M39Lt439 AHvvluwm K M H0ng 012 ALL L1 6 01 m e 9 T 1th 3 43 ANb 41 1 tf TUNING 4 A6 Hut0710M 0F 4n W x E Wt Lt 5 x Lquot 1 21W i 39 1 M HOW 2 mm RISLATEV To POIEVUTAL pEMF Z A Lg P IIM ZW39M ql LIL WI wonEr w LELTuZE 1 m m gt y M Le gt4 HOTIUA THA Mt CA W MA A QM my A ixt 4 5t 74W5l L55 Wt Q M in ELA Wt Mk c D l quot PROOF v LL 39 e h jquot g my WM 1M n w L L Wifz Zquot AIMl 111 VEL 1 Valquot V 4 t m a 211 3 POTENTIAL BASED Meow I S Wm Dd AMuu n ulL T 2 mg A quotmm M 1 Wi P w L O l H TELESCOPIMQ hr 2 Ln Lguukgl T Ms Z Uq 39 t3 pt pt 1H lM 1 L beL PL A mm A Li b A a WR 5 39 gt T m A W v 4 3v 6 F Lu 2 w 6 v M m Lm z n 411 WM 4 LgHWQA 1 1 my n r V gt f M f fig E quot 02 Lh WKMWWMWvawm 4 l w er A 9 5 Li 39 39 I u ZWLT H w 7 7 PM 33 3Mag LIAEAR REGZEQCIOIU M n f I 0 w 395 n c 4 t A 5 X t ON um Mm wwwugg u Hess l g 30 1 Elm INCMAJCG Xt Pf z m f i 2 am misfit 3 meta Lose 91 quot 9N LtlJDATE Got To LIA GOAL 39 THE TO 7M Lassa 3 739Hi3901 c i ril A SHOMLD M07 Br Mme4 LARGE2 THAU 7mg TOML um 0r HI OPPJUL AL v s Qllg312glgzmUziUT i T x A quotVti 7th IMF v iii it my 391 W i r mef quot quot7 39 u 4 My K TD Tr L BICJ D l7 739 0 A P K 0 g 0 1 0R LI VIE ALE 011 LHUF IAN 3912 H ow 1 o gum413 3131713 3 r w 2 v 2 W4 2 IA WVUQH 47quotU39x wiltx A V V H My x lquot V W 339 U1 C 3901 N t ICC 91 l ST f5 RC7 Wt IFXAll MnE 7 19A 1 m 1 PA I e AME 7 I3 IQ 2 0 pl r r LVN 173 U Xt Kt amp w 17 THUS LL Lukquot V 5 21 Jt339xt l NEU OLD 5 sremn W Z 09 I HA i In W 2 R ATE CL Wt 14 Wtyt 4 I V6 bu Imam r H w r u p mm a R A l 51 quot139 3 3quot C quotif it LEVquot use 1 DIFFERENT b IFerfUNE 7 2 y 39 W v WWW 44 w 124 4 but LUL 4 39L El Vt 9 3 L l 7 ENE fITgD 10 A 5 V W mommy WIEWIWS 9 i 01 1 Jr 739 Xf i 3 u i W 39L m AILug v u hLH W 7 LiHum ya Xim m M Lww Xt Bit 3 Xtir LU if M 739 LU quotL V12 H21 2 Xi V llLl Q N LKMCiZIltHl2flgt y39 aw 2 H 114 HemmUT 7 CA J lt M l 1 gtwenAL 090 9 0 MLMW Wuv my 1 quotlquot 01339 u g LV 1 5H Wx s Vl quot W1 j H 39xv i X1 6 Wi P V L b7 llWQ V17 EGU K k r LLquot Y quot gt I lllhr lt LU 1214 Lt1 739 Aft I Ni 4 I A I r r 12 f 39 L mm M lt 139 IMPLILIT L 391 1014 1 ll U J Ll fr W 4 Lin r 1 HIM H l X PM 7 A P DAT r u m i mm m J w lei rm ML PctEm W PC l 139 VE IQl IN 435 mwg 1 quot L l l R A N 6 LM I WITH IAM N39lt i FIMSlww 1 7 f UCWO V 6 PERU PIYBGKI AKA I4 I 1 110R t 127 GE XL A 41 IF wix ra m E GM guumw LABEL ate 1 Hi my 1 L 1mg WH I W t N L fl Ut 439 11 EN Xi V q H k H i 393 if UH Wt39H 39 W 4 U XL 6 I M W H HF mad 396 UPDATE Angz I IN I QV A A F 139 Cowgcrrewzww A w 5 A I39A39Ec quot M LIAMAR HIMMI A096 GD LIPMm oz ae z3 MA ff Am quot Lu A A 011 ZrIg m Ki Nilif ixquot 5i L EH bi4 39A H f39 t I3 A A I w I M A W 2 U0 x T quotHi MIS39HW39E LU41LV iz z x A 1 m wt SPA Oil1quotquot NOW Wi 3amp0 53 IMOe K 2 t f V Lui I J g WM quot 9 W I A 5 2 W Ag w w go V 393 ng RE f 3 NH 7 l i i i 7 g 5 39 2 MUm 393 Wt fr 45 f I 5 w a Ur mi L gt2 L d f w J I g a h x I l f 5T L J I 1 quot AU 3X H 39 t j 1641 LUi f39li T 1 39 7 M zft U gt Xi I m m quotW 1 ti Vquot me v A WH39IM Lytlb e V Sume me rs l G S 1 xh ayzaxmnym0M w in lm xi 6 Mmquot H e I l I W U l M l quotLquotquotquotquotquot39 quotquotquotquotquotquotquotquotquot1quot L M v VUIXquot9t r I LUi 9 J W1 UW lt 3 er xviiquot 1W LIN W 9 X a J I I 0 ME Aquot i Aquot 51 1 r mEuw AK Fm aeAJz eq L mm L war I w V gt hm f gftl Vin Q LV14 IL 1 v Wu role Wit62E 4 099 3 5 Wm 13c N i cM U 8 I 43913 WE i i3 MN 0 5 W I MANv 3 LE U X f39 If A 9 Wm 1557quot MN J Kt A MN UGX COMBMAW or ass3t w 1 MWSKTG 61 1911ng I A PM 41 DAMN I Equot is rip L KLl l iv4y DUL 1 I quot OPE U in I I 513 MA L l 2 H f xi Lt 3 bxponentiated gradient wrh X HO ti 39it Corr 7 m i muUP w a 5117 Algorithm EGfUss n Parameters L a loss function from R X R to 000 U I the total weight of the weight vectors 5 and s a pair of start vectors in 0 UN with gigs sf 1 and 77 a learning rate in 000 Initialization Before the rst trial set wfL Us and w Us Prediction Upon receiving the ith instance xi give the prediction 37twf wtquotxt Update Upon receiving the tth outcome yt update the weights according to the rules w r i t i wt1x U N 38 211 WETij wtj quottj Wart wt1i 39 N 39 31 133 wt m where TI eXP TILIy tUmti 310 1 M exp 0L2ytUtiT 311 1 Figure 3 Exponentiated gradient algorithm with positive and negative weights EGUssn I x MPH lquot J PHIH 20 MALClquot V43 XPLCIT H 9390 x a 7 39 Mm 9on 2 alwwwil gt 44 MW Lava15 W Wm iytw M LIL WU X g t A lvt1l JPN Ltg wkB Xt WW4 CN btif 392 H wquot W 17 4 4103 W c 9 0 T W WL 51 WUX gt w 1 0mm Mir02 0F 1 w l H E Wt W L 91 mme m Wt W H U L XVHcM Mmcm Woowe froHi FIRMPING 1 Mm 5 115 quotMW I 4 I 11 r WM 7 3 1 0png W0 095 D fro8M 30LlIquotiCU N x3 Xvquot 0 ACC m It WM AH K A pMH wwww N AngonVL M4157 HM P E a PRIME N P 2 ED a f mop CPl3EQquotf3 i a Mr MGDN M c anew mama 3939 3939I I 1 15 uh u I Nonsecret Key Cryptosystems Rea mathematics has no effects on war No one has yet discovered any warlike purpose to be sewed by the theory of numbers G H Hardy The Mathematician s Apology 1940 Q Today s class I Public key cryptography I One way functions I Number theory I Fun with primes I Finding primes I RSA algorithm I El Gamal I Elliptic curves CMPS 290x UC Santa Cruz Spring 2001 2 i Publickey cryptography I Private procedure E I Public procedure D I Identity E D m D E m m I Secure cannot determine E from D I Base techniques for E and D on I Discrete logarithms I Factoring I Other stuff CMPS 290X UC Santa Cruz Spring 2001 i RSA in one slide I Numbers in red are secret I All other numbers are public I RSA algorithm is EM Me mod n D C Cd mod n npxq pqareprime d is relatively prime to p lq l e xda 1 mod p lq 1 g CMPS 290X UC Santa Cruz Spring 2001 1 RSA in Perl print packquotCquot splitD echo quot16iIIoUz p0pp0punpackquotHquotltgt ifEsMsKsNolN1lKd2Sa2d0 7 ltXdlMLa lN0dsXxlMlN ldSMOltJdSJXpquotdC Today RSA may be exported but only with 512 bit keys 3 CMPS 290x UC Santa Cruz Spring 2001 5 1 More on public policy amp RSA Because computer source code is an expressive means for the exchange of information and ideas about computer programming we hold that it is protected by the First Amendment Sixth Circuit Court of Appeals April 4 2000 Ruling that Peter Junger could post RSA source code on his web site 6 CMPS 290x UC Santa Cruz Spring 2001 6 Oneway functions I A one way function is like mixing paint I Easy to mix the paint I Difficult to unmix get back yellow amp blue paint from green I Simple example of a one way function I Middle 100 digits of n2 k where n is a random 100 digit number I Given n easy to calculate k I Given k hard to calculate n I Does a given k map to only one n I Application I Pair k and n where k can be given to everyone but only g the key owner knows n CMPS 290X UC Santa Cruz Spring 2001 7 Properties of E and D I Trap door one way function I DEM M I E and D are easy not difficult to compute I Doesn t automatically mean fast I Revealing E doesn t provide an easy way to compute D I Trap door one way permutation also true that I EDM M g CMPS 290X UC Santa Cruz Spring 2001 8 Property 1 DEM M EM Me mod n DEM Me mod nd mod n Med mod n Question can we choose 6 d and n such that M E Med mod n CMPS 290X UC Santa Cruz Spring 2001 9 i M 5 Med mod n amp Euler s totient function I We want M E Med mod n This is equivalent to saying 1 5 Medquot1 mod n Reason M 1 a MMed391 mod n I Euler and Fermat say that MWquot 5 1 mod n where qgt n is the Euler totient function Proof omitted for brevity I Euler totient function qgt n number of positive integers lt n that are relatively prime to n If n is prime qgt n n 1 because all integers lt n are relatively prime to a prime number CMPS 290X UC Santa Cruz Spring 2001 10 Properties of Euler s totient function I p x q p x q for p q non identical prime numbers ITherearepxqp1q11 pxqpq1 pI x qI numbers below p x q that are relatively prime excluding p1 multiples of q q1 multiples of p I We are trying to find 1 5 Med 1 mod n I We know that 1 E MW mod n I Euler s generalization of Fermat s little theorem I Seted 1 nchoosenpxq I ed n1npq I How do we choose 6 and d CMPS 290X UC Santa Cruz Spring 2001 11 Where s Mr ED We need to choose e and d such that ed n1npq Pick a random 1 relatively prime to n I In other words gcd n D 1 Since d is relatively prime to qgt n it has a multiplicative inverse 3 mod n d x e E 1 mod M n This means that d x e k x qgtn 1 for some k Thus Me mod n MWquot mod n and I 1 2 MW mod n according to Euler I 1 2 MW mod n I 1 2 Med 1 mod n I ME Med mod n Problem solved ME Med mod n CMPS 290X UC Santa Cruz Spring 2001 12 i Properties of E and D I Trap door one way function DEM M gtE and D are easy not difficult to compute Doesn t automatically mean fast Revealing E doesn t provide an easy way to compute D I Trap door one way permutation also true that I EDM M g CMPS 290X UC Santa Cruz Spring 2001 13 Property 2 easy to compute EM Me mod n Easy Every 8th grader can do exponents Every 4th grader can do mod n I How big are M e and n n M and 11 must be big 10100 for security Smaller values may be too easy to factor 10100 z 2333 gt 333 bit numbers 6 need not be as large ed l nznforprimen CMPS 290X UC Santa Cruz Spring 2001 14 i Doing fast exponentiation I aInn am x an I ab ab2 x ab2 if 2 divides b I So can compute Me in about logze multiplies I For 6 around 21024 we need 1024 multiplies I This is doable for a computer I A 4th grader might have problems I Faster bitwise algorithms known CMPS 290x UC Santa Cruz Spring 2001 15 i Anything else hard to compute I We need to find large prime numbers p and q I Obvious way Pick big number x fori2tOx 1 if i divides x it s not prime start over with x 2 Even integers aren t prime done x is prime I Problem this is slow CMPS 290x UC Santa Cruz Spring 2001 16 EL How many prime numbers I Infinite proved by Euclid 3OOBC Proof by contradich Suppose that there exist only finitely many primes P1ltPzlt ltPr LetN P1P2Prgt2 The integer N1 being a product of some primes has a p medivisorpl1ltilt r nwithN So pl divides N N1 1 no divisors this is a contradiction ah Dens ty of primes 1X for 05x 51000 Mr is the number of primes s x v me hnpjwww utm ed ureseamhpnmeshwmany 5mm a Approximating rcx The Prime Number Theorem Icx xln x So to find a prime bigger than x we need to make about In x2 guesses Each guess requires x work I Not really true because some numbers can be ruled out quickly For 200 digits worst imaginable case 230 guesses x 10100 This won t be done any time soon CMPS 290X UC Santa Cruz Spring 2001 19 i Need a faster prime test There are several fast probabilistic prime tests Can quickly test a prime with high probability with a small amount of work Most commonly used today is Rabin Miller Choose a random odd number p to test Calculate 9 such that 2bE is the largest power of 2 that evenly diVides p l Calculate m such that p l 2 x m CMPS 290X UC Santa Cruz Spring 2001 20 MillerRabin primality test I Execute the following test I Choose a random number a such that a lt p I Setj0 andzzammodp I Ifz l orzp lppasses thetest I Ifj gt 0 and z l thenp isn t prime I Whilez p l and jltb I Setzz2 modp I Ifz p 1thenp passes the test I Ifjgt 0 and z 1thenp isn t prime I Ifj b andz p lthenpisn tprime I If p passes the test it is prime with probability 34 I If p passes k tests it is prime With probability 1 14k CMPS 290X UC Santa Cruz Spring 2001 21 Speeding up testing I Miller Rabin test is fast but finding primes can be faster I General procedure is I Generate a random nbit number p I Set the highorder and loworder bits to l I High order bit ensures the number is n bits long I Low order bit ensures the number is odd I Check for divisibility by small primes I Small primes are up to 256 or faster 2000 I Keep a table of the small primes I Perform the MillerRabin test repeatedly for random values of a as long as p passes them I Use small values of a to make testing faster g I Repeat as often as desired to ensure that p is truly prime CMPS 290X UC Santa Cruz Spring 2001 22 Largest known prime Digits in Largest Known Prime in the computer age nnnnnn nn uuuuuu uu 1000000 100000 10000 1000 0 1950 1960 190 1900 1990 2000 2010 Year by Chris K Caldwell CMPS 290X UC Santa Cruz Spring 2001 23 Properties of E and D I Trap door one way function D E M M E and D are easy to compute gtRevealing E doesn t reveal an easy way to compute D I Trap door one way permutation also gtE D M M g CMPS 290X UC Santa Cruz Spring 2001 24 Property 4 E D M M DM Md mod n EDM Md mod n6 mod n Mde mod n Med mod n M from the property 1 proof CMPS 290X UC Santa Cruz Spring 2001 25 i Property 3 Revealing E doesn t reveal D I Revealing E e n I Can an attacker find D I If attacker factors n p x q I exdalrnodp lq l I Easy to find d E equot1 mod p lq l I Use experience to argue factoring is hard I Argue all other attacks are at least as hard as factoring n g CMPS 290X UC Santa Cruz Spring 2001 26 i Original RSA challenge 100 prize Appeared in Martin Gardner s Scientific American column August 1977 n RSA 129 1 1438 1625 7578 8886 7669 2357 7997 6146 6120 1021 8296 7212 4236 2562 5618 4293 5706 9352 4573 3897 8305 9712 3563 9587 0505 8989 0751 4759 9290 0268 7954 3541 e 9007 C 9686 9613 7546 2206 1477 1409 2225 4355 8829 0575 9991 1245 7431 9874 6951 2093 0816 2982 2514 5708 3569 3147 6622 8839 8962 8013 3919 90551829 945157815154 CMPS 290X UC Santa Cruz Spring 2001 27 i 40000000000000000 9 17 Ron Rivest 1977 Factoring n 129 digits would require at least 40 quadrillion years if you could do a x 9 mod 3 in one nanosecond Derek Atkins April 1994 We are happy to announce that RSA 129 3490 5295 1084 7650 9491 4784 9619 9038 9813 3417 7646 3849 3387 8439 9082 0577 x 3 2769 1329 9326 6709 5499 6198 8190 8344 6141 3177 6429 6799 2942 5397 9828 8533 g CMPS 290X UC Santa Cruz Spring 2001 28 How d they do it so fast I Better factoring algorithms I Fastest known in 1977 was Pollard Rho Pollard75 I To find factor p requires 4p modular multiplies I Worst case lowest p is n we need 4 n multiplies I For RSA 129 13 1032 4 1015 years I Rivest probably used this but made a math error 4 quadrilllion gt 40 quadrilllion I Better algorithms today such as number factoring sieve I Distributed computation I Can provide improvements of about one million by farming the problem to multiple computers I Still can t do a X 17 mod 0 in one nanosecond not faster processors I lns 10 9 s I Best processors today 1 GHZ cycle lns g I But multiplying 100 digit numbers takes many cycles CMPS 290X UC Santa Cruz Spring 2001 29 Quadratic Sieve I To factor n find x and y such that x2 E y2 mod n I Then n divides x2 y2 x y x y I Thus n gcd nx y x gcd nx y I If we re lucky factors will be non trivial I If x and y generated randomly probability is since n has 2 prime factors CMPS 290X UC Santa Cruz Spring 2001 30 i Breaking RSA 129 I Organized by Derek Atkins and others 1994 I Quadratic Sieve algorithm I Memorylimited 1994 most workstations had 16MB RAM used 10M to hold 05M primes I Recruited volunteers from Internet I 1600 machines I Used 5000 MIPS years over 8 months CMPS 290X UC Santa Cruz Spring 2001 31 i Recent factoring algorithms I Team from CW1 Amsterdam factored RSA 155 512 bits August 1999 I 8000 MIPS years 36 CPU years I 7 months on 300 machines I Used Number Field Sieve I Challenge problem factor RSA 300 for an automatic A in the class How much harder is this CMPS 290X UC Santa Cruz Spring 2001 32 i RSA security I Factoring is hard gt RSA is secure I Can you compute D without factoring n I Probably not but we can t prove it I Can prove other mathematical attacks are equivalent to factoring ard gt RSA is secure CMPS 290X UC Santa Cruz Spring 2001 33 3 Determine d without I Brute force In digits long amount of work is 10 quot I Try lM second special purpose hardware I Will take 3x1036 years for m 50 I For factoring difficulty m gt 100 I Non brute force knowing 0 enables factoring I ed 1 mod n k n ed l I But finding n is same as factoring I Also true for multiple of n CMPS 290X UC Santa Cruz Spring 2001 34 Properties of RSA S E and D I Trap door one way function D E M M E and D are easy to compute Revealing E doesn t reveal an easy way to compute D next time I Trap door one way permutation also EDMM CMPS 290x UC Santa Cruz Spring 2001 35 Key management I Public keys only useful if you know that I The key matches the entity you think it does I The entity is trustworthy I Approach 1 public announcement I Publish keys or digests in a public forum I USENET groups I Email messages I New York Times classifieds I Problem easy for intruder to pretend to be someone else I Approach 2 public directory I Trusted authority has directory mapping names to public keys I Entities register public keys with authority in some way I Authority publishes directory I Allows secure electronic access more on this next lecture I Print using watermarked paper or other secure mechanism g I Approach 3 certificates CMPS 290x UC Santa Cruz Spring 2001 36 i Applications of RSA Privacy Bob encrypts message to Alice using E A Only Alice knows D A Signatures Alice encrypts a message to Alice using D A I Bob decrypts using E A Knows it was from Alice since only Alice knows D A g CMPS 290X UC Santa Cruz Spring 2001 37 Other public key algorithms knapsacks Based on an NP complete problem knapsack packing Private key superincreasing knapsack Public key private key with each weight converted by kl sin mod m m is greater than the sum of the sl n has no factors in common with m Encrypt by computing weight for each block Decrypt by multiplying by n 1 mod m and partitioning using private key Problem Shamir amp Zippel found a way to convert public key into private key CMPS 290X UC Santa Cruz Spring 2001 38 Program Checking Lec rur39e 9 3 Feb 2004 290G Lecture 9 The Idea Sof rware should check i rs own work When The answer is compu red check Tha r if is The correc r answer Jus r as we check our own work Do sums forwards and backwards Doubleentry bookkeeping 3 Feb 2004 290G Lecture 9 2 What Does It Mean To Check Say fgtlt y How can we verify y fx Wan r To do This quickly Comple rely no r a par rial check 3 Feb 2004 290G Lecture 9 What Does It Mean to Check Say procedure px implements a function fx if we compute y px then we should have y fx How can we verify y fx multiple implementations and voting testing static analysis onne independent checking 3 Feb 2004 290G Lecture 9 4 Simple Checkers Procedure px implemen rs func rion fx Have a checking procedure Cxy wi rh Cxy True S fx y WiTh high probabiliTy if C is randomized 639 is asymp ro rically fas rer Than 7 We call is a checkerfor f 639 is also an execufabe spec ca on for f 3 Feb 2004 290G Lecture 9 ExplanaTion Why should C be fasTer Than 1 Two reasons PracTicaIiTy AsympToTically checker has negligible cosT Theory Forces The checker To be differenT from The program 3 Feb 2004 290G Lecture 9 Example Factoring Integers Problem fac ror a large in reger Believed To be very hard Checker Mul riply fac rors roge rher More generally any problem in NP has a PTime checker O rher examples 3 Feb 2004 290G Lecture 9 Another Example Sor r an array of numbers How do we check This Need Two Things Elemen rs are ordered Elemen rs are a permu ra rion of original array CompuTe checksum of bo rh arrays and compare Sor ring is On log n bu r checker is On 3 Feb 2004 290G Lecture 9 And Another Example Problem Is k in sor red array A Algori rhm Binary sear39ch r39e rur39n yes no Problem This is noT efficienle checkable Solu rion Change The oquuT To give index inTo ar39r39ay This gives a consTanT Time check 3 Feb 2004 290G Lecture 9 Interface The last example is instructive Sometimes we must augment the output with extra information to enable efficient checking This is a general technique What can I add to the output to make it verifiany correct 3 Feb 2004 290G Lecture 9 10 Propositional Satisfiability Complicated expensive SAT solver39 finds a satisfying tr39uth assignment for a given boolean formula Have a separate lineartime routine to ensure the truth assignment satisfies the original formula 3 Feb 2004 290G Lecture 9 11 Theorem Proving Au romo ric Theorem Prover produces a proof of The conjec rure Theorem provers are of ren big complicated and un rrus rwor rhy Have a seporo re and simple proof checker 3 Feb 2004 290G Lecture 9 12 And Another Example Transla rion valida rion Is my compiled program fai rhful To The original A very widespread lowlevel problem Limi rs wha r compiler wri rers will a r remp r A research subarea of i rs own recen r 3 Feb 2004 290G Lecture 9 13 Translation Validation Sketch A compiler proves To ifself Tho r The source and forge r programs are equivolenf Make This proof explici r And por r of The ou rpu r Proof checking is relo rively easy In confros r ro proof discovery 3 Feb 2004 290G Lecture 9 14 Proof Carrying Code Compiler produces binor39y execuToble TogeTher39 wiTh pr39oof ThoT The execuToble soTisfies a given secur39iTy specificoTion Each clienT downloads execuToble and quickly checks pr39oof To verify ThoT The code soTisfies The secur39iTy specificoTion no need for39 Tr39usT 3 Feb 2004 290G Lecture 9 15 Randomness Randomiza rion of ren gives very simple and fas r checkers Problem Calcula re A x B C Le r r39 be a randomly chosen small pr39ime Check A mod r39 x B mod r39 mod r39 C mod r39 3 Feb 2004 290G Lecture 9 16 Why Does This Work A mod r39 x B mod r39 mod r39 C mod r39 If A x B does equal C Then The clear39ly holds from axiom A mod r39 x D mod r A x D mod r IfoBC39ThenCmodr39 C39modr39 WiTh high pr obabiliTy Small number muITipIiesmod can be done fasT This is The example applicaTion To The PenTium bug 3 Feb 2004 290G Lecture 9 17 Checking Division Given N D division compu res Q R N numera ror D denomina ror Q quo rien r R remainder NDXQR if and only if NRDxQ Reduces To checking mul riplico rion 3 Feb 2004 290G Lecture 9 18 Comparison with Other Techniques The paper39s dr39aw comparisons To sever39al o rher39 approaches Verifica rion Asser39Ts Tes ring Faul r Tolerancequot 3 Feb 2004 290G Lecture 9 19 Verification Verifica rion proves correc rness for a inpu rs Before The program is run in produc rion Checking proves correc rness on one inpu r The one we care abouf Bu r This is largely a s rrawman Full verification is only used in special si rua rions 3 Feb 2004 290G Lecture 9 20 Asserf Programming Many programmers use asser rs Really The cul rure of checking Paper acknowledges rhe connec rion Bu r paper focuses on asser rs Tha r are more comple re more focused on func rional behavior par ricularly efficien r 3 Feb 2004 290G Lecture 9 21 Testing Tes ring and checking bo rh Try To find errors Checking is AuTomaTic Runs everyTime Rigorous says yes no correchy AT leasT if checker is correcT Which is more effective Are They complemen rary Checking makes The TesT suiTe more effecTive and vice versa Do we wan r bo rh 3 Feb 2004 290G Lecture 9 22 Digr39ession The Pentium Bug To produce Pen rium In rel used of leos r Ver39ifico rion Aufomm ic complafl39on of lugHe ve equafons 7 0 0wer e ves of circa397 a e5y7 Tes ri ng Presumaby very in fensve Bu r nei rher39 approach found The bug Checking migh r have found This one 3 Feb 2004 290G Lecture 9 23 Fault Tolerance Mul riple differen r implemen ra rions Drawbacks Very expensive Slow andor parallel hardware requirements No assurance dis rinc r implemen ra rions aren39T correla red Example The space shu r rle or Arianne 5 3 Feb 2004 290G Lecture 9 24 Correctors Don39T jus r find bugs fix bugs How can we do Tha r Randomiza rion is The key 3 Feb 2004 290G Lecture 9 25 Sketch Here39s The game Given procedure px which compu res correc r answer for fx wi rh known probabili ry The correc ring program uses p as a subrou rine Idea Use mul riple calls ro p ro calcula re The answer in differen r ways Cons rrain r Only allowed a cons ran r fac ror increase in running Time 3 Feb 2004 290G Lecture 9 26 An Example Consider mul riplica rion o x b Over39 a fini re field Choose random numbers r1 r2 Colculo re 0 r1xb r392 a r391xr392 r391xb r392 r391xr392 0 39r391 r391 x b 39 r392 r392 ax b 3 Feb 2004 290G Lecture 9 27 Why Does this Work a r391xb r392 a r391xr392 r391xb r392 r391xr392 Each multiplication is a random pair39 With respect to ab So each is correct with a known probability p Sum is wrong bounded above by probability 41 p Repeat trials to increase probability to desired level 3 Feb 2004 290G Lecture 9 28 Opinions on Connectors This sounds like a crazy idea How of ren is mul riplica rion buggy How of ren is my problem a fini re field The idea is probably crazy 3 Feb 2004 290G Lecture 9 29 CorrecTors HisTorical Example BuT people have Tried To build correcTors for complex problems Consider a hisToricaI example where The oquuT is humangeneraTed BuT could be machine generaTed PLC was a PL1 compiler developed aT Cornell In The days when compilaTion was expensive AuTomaTically correcTed errors in program Always yielded a valid program close Toquot The one The programmer enTered 3 Feb 2004 290G Lecture 9 30 PL C The experience wiTh PLC was ThaT auTomaTic correcTion didn39T work The furTher a program was from a valid program The more bizarre The oquuT Example To be or noT To be ThaT is The quesTion quot Compiles To begin endquot The idea died as compilers goT fasTer 3 Feb 2004 290G Lecture 9 31 A Use of Correction in the Real World There are two kinds of bugs Deterministic These are repeatablewe can find and fix these Nondeterministic Timing bugs Must get lucky to fix one of these For a nondeterministic bug just try again Standard in commercial databases This is a form of automatic correction Note Requires failstop semantics though 3 Feb 2004 290G Lecture 9 32 Conclusions about Correction No r obvious how To apply The idea in full To a complex sys rem Bu r a useful idea for39 specific pr39oper39Ties Nondeferminis ric bu r de rec rable bugs 3 Feb 2004 290G Lecture 9 33 Back To Checkers Each CS communiTy has own view of sofTware developmenT Programming languages The answer is The compiler ie sTaTic analysis OperaTing sysTems The answer is The 05 Le dynamic analysis caches SofTware engineering The answer is in The developmenT process Theory The answer is asympToTic complexiTy randomizaTion 3 Feb 2004 290G Lecture 9 34 Back To The DefiniTion A checker for f is a program C ThaT VerifiesrefuTes ThaT fx y correcTIy Does so in asymptotically less Time Than 1 Examine The assumpTions underlying This approach 3 Feb 2004 290G Lecture 9 35 Assumption The Specification Checking 1 requires we know f39s specification Comple rely no r jus r por riolly There is no big sys rem for39 which we know The full specifico rion por riolly explains why The examples are all Tiny neo r problems Would checking parfbspecifico rions be useful 3 Feb 2004 290G Lecture 9 36 AssumpTion FuncTions Assume programs are inpuToquuT funcTions BuT This is noT realisTic MosT imporTanT sysTems are sTream Transducers Takes i npuT sequence produces oquuT sequence Need noTion of correcT behavior up To a poinT in Time 3 Feb 2004 290G Lecture 9 37 AssumpTion AsympToTic ComplexiTy is Crucial Checker musT be asympToTically fasTer GreaT if iT is buT is This required In pracTice happy if checker is 10 of Time of Time To compuTe answer BuT asympToTic requiremenT is useful Forces criTicaI Thinking in asserTs More likely To have orThogonal checker 3 Feb 2004 290G Lecture 9 38 LECTumEtw OML1NE MA BAQICS z VECTOR X 1 512 e R a 44k m A A z HA rim SQMARWMmx A 2g zz Aim 3 4A x 14 I A SYMMETRQC w A Kr 39 TEAHQPOSE A6 A3 Val u ammwmi g a r Iagui f quot VA h m 51 E 52 amp gm m 55 m z c A Be A MAME a A Maw R asw ww out wrvmmmmmwbm 3 Marlowm r x g W a 7 1 f 9 vi a m g 392quot 3 f Z quotquot 39 4 quot TZXLUMEQA I 1 Lh mfg TT W CGLMM M f 1 Z 3V Mild A 2 g a A u 3A m r iquotMj TRM a EsGEMUELT g A EIQENUALME S an x gymv vgmWur 7 5 Wyame g MK 6 m E u M X My M WU 55 PEI E w M A x P WITH ONE EfGENUALME g W k MW M in link a SW4 0 2 M203 Em W 3 Q ER a 3 1 Elite am ai a MMquot WEQWQ 39 L4 1 if g Mkm RAMki Pkea w f 3 QM w EXEELWW a 5 AN 593 MME m Q i J 11 A Ra G if g 2 a V W w at t 5 Eg g M w I v Satisfying Er39r39or39 Conditions 3 Lecture 15 24 Feb 2004 290G Lecture 15 Overview of Verification Architecture Verification T6 C Ergo 39 39 on Ion Specification Condl rlon I checkSatLitsArith I EC 62432 s t39sf39 b39l39t aclhelcakelrl y CheCksa Ts I checkSatLItsEquaIIty I coopera ng I I I checkSatLitsArrays I procedures SAT solver DavisPutnam 24 Feb 2004 290G Lecture 15 2 EC Satisfiabilify Checker ab fafb ac fafc Sa r o o o o o o o o 1 o o o 1 o o o o 1 1 o o 1 o o o o 1 o 1 o o 1 1 o o o 1 1 1 o 1 o o 0 X0 1 o o 1 o 1 o 1 0 X0 1 o 1 1 o 1 1 o o o 1 1 o 1 o 1 1 1 o 1 1 1 1 1 o 24 Feb 2004 290G Lecture 15 ab A fa f b bC fa fc J 1 02b fafb l 1 1ab 1afb ExplicaTed Tau rology removes many oTher Tru rh assignmen rs 3 Overview of Verification Architecture Verification T6 C Ergo 39 39 on Ion Specification Condl rlon I checkSatLitsArith I EC 62432 s t39sf39 b39l39t aclhelcakelrl y CheCksa Ts I checkSatLItsEquaIIty I coopera ng I I I checkSatLitsArrays I procedures SAT solver DavisPutnam 24 Feb 2004 290G Lecture 15 4 checkSatLitsArith Difference Constraints A special case of linear arithmetic All constraints of the form X C I y c is a constant Special variable 2 representing 0 Example X 0 y x lt y y4 lt w w2 lt x A w1lt 2 Z 1 W 24 Feb 2004 290G Lecture 15 ifsEquany checkSafL xgx x X A 99999gtlt Consider ggx 290G Lecture 15 24 Feb 2004 Overview of Verification Architecture Verification T6 C Ergo 39 39 on Ion Specification Condl rlon I checkSatLitsArith I EC 62432 s t39sf39 b39l39t aclhelcakelrl y CheCksa Ts I checkSatLItsEquaIIty I coopera ng I I I checkSatLitsArrays I procedures SAT solver DavisPutnam 24 Feb 2004 290G Lecture 15 7 Cooperating Satisfiabilify Procedures Consider equali ry and ar i rhme ric m y n XSy yzSX OSZ l ltX X2137 fXlfY 0 Xgt1HYZ Z false lt ffX fy fZ 24 Feb 2004 290G Lecture 15 NelsonOppen Method 3 3 Broadcas r all discovered equali ries and rerun sa r procedures UnTil no more equaliTies are discovered or a con rradic rion arises xQo n rradic rion 24 Feb 2004 290G Lecture 15 Overview of Verification Architecture Verification T6 C Ergo 39 39 on Ion Specification Condl rlon I checkSatLitsArith I EC 62432 s t39sf39 b39l39t aclhelcakelrl y CheCksa Ts I checkSatLItsEquaIIty I coopera ng I I I checkSatLitsArrays I procedures SAT solver DavisPutnam 24 Feb 2004 290G Lecture 15 10 Theory of Arrays Syn rax and informal seman rics If E deno res an address and p a heap s ra re Then selpE denoTes The conTenTs of memory cell updpEV denoTes a new heap sTaTe obTained from p by wriTing V aT address E Decision procedure implemen rs following rule x y gt selupdp x v y v x i y gt selupdp x v y selp y whaT if x y is unknown 24 Feb 2004 290G Lecture 15 11 Theory of Arrays Syn rax and informal seman rics If E deno res an address and u a heap s ra re Then seluE denoTes The conTenTs of memory cell upduEV denoTes a new heap sTaTe obTained from u by wriTing V aT address E Decision procedure implemen rs following rule x at y V selupdu x v y v x v v S UPdH x v y sew y whaT if x y is unknown nonconvex fheory inpuT facTs enTail disjunc rion of equaliTies buT do noT enTail any individual equaliTy can add SAT liTeral xzy 24 Feb 2004 290G Lecture 15 12 Overview of Verification Architecture Verification T6 C Ergo 39 39 on Ion Specification Condl rlon I checkSatLitsArith I EC 62432 s t39sf39 b39l39t aclhelcakelrl y CheCksa Ts I checkSatLItsEquaIIty I coopera ng I I I checkSatLitsArrays I procedures SAT solver DavisPutnam 24 Feb 2004 290G Lecture 15 13 TypeBased Race Detection for Java 15 Jan 2004 290G Lecture 4a 1 27 Programming Wi39rh Threads Decompose program in ro pieces Tha r can run in paraHeI Advan rages exploi r mul riple processors Threads make progress even if o rhers are blocked Web Server ne rwork 15 Jan 2004 290G Lecture 4a 2 27 Mul39ri39rhreaded Program Execution Thread 1 Thread 2 t1 hits t2 hits hits t1 1 hits t2 1 1391hi139s hifs13911 1392hi139s hifs13921 hlfs0 0 0 0 0 0 hn szz 1391hi139s 1392hi139s hifs13911 hifs13921 hITS0 o 0 c 0 o hl139s1 15 Jan 2004 290G Lecture 4a 327
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'