United States Patent [19J
`Scan dura
`
`111111
`
`1111111111111111111111111111111111111111111111111111111111111
`US006061513A
`[11] Patent Number:
`[45] Date of Patent:
`
`6,061,513
`*May 9, 2000
`
`[54] AUTOMATED METHODS FOR
`CONSTRUCTING LANGUAGE SPECIFIC
`SYSTEMS FOR REVERSE ENGINEERING
`SOURCE CODE INTO ABSTRACT SYNTAX
`TREES WITH ATTRIBUTES IN A FORM
`THAT CAN MORE EASILY BE DISPLAYED,
`UNDERSTOOD AND/OR MODIFIED
`
`[76]
`
`Inventor:
`
`Joseph M. Scandura, 1249 Greentree
`La., Narberth, Pa. 19072
`
`[ *] Notice:
`
`This patent issued on a continued pros(cid:173)
`ecution application filed under 37 CFR
`1.53( d), and is subject to the twenty year
`patent term provisions of 35 U.S.C.
`154(a)(2).
`
`[21] Appl. No.: 08/914,314
`
`[22] Filed:
`
`Aug. 18, 1997
`
`Int. Cl? ........................................................ G06F 9/44
`[51]
`[52] U.S. Cl. .......................... 395/701; 395/702; 395!705;
`395!703; 395!708
`[58] Field of Search ...................................... 395/701-712
`
`[56]
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`5,528,491
`5,790,863
`5,812,853
`
`6/1996 Kuno et a!. ................................. 704/9
`8/1998 Simonyi .................................. 395/707
`. ... ... .... ... ... ... ... ... 395/708
`9/1998 Carroll et a!.
`
`OTHER PUBLICATIONS
`
`Aho et al., "Compilers Principles, Techniques, and Tools",
`Addison-Wesley, pp. 287-293, Mar. 1988.
`C.A. Welty, "Augmenting Abstract Systax Trees for Pro(cid:173)
`gram Understading", IEEE, pp. 126-133, Jan. 1997.
`Canfora et al., "A Reverse Engineering Method for Identi(cid:173)
`fying Reusable Abstract Data Types", IEEE, Mar. 1993.
`
`Primary Examiner-Tariq R. Hafiz
`Assistant Examiner-Todd Ingberg
`
`[57]
`
`ABSTRACT
`
`Disclosed herein is a method, which can be automated on an
`information processing device with memory, that dramati(cid:173)
`cally reduces the effort required to create systems for reverse
`engineering source code in a plurality of structured lan(cid:173)
`guages into Abstract Syntax Trees (ASTs), which represent
`all of the information in said source code, and to automati(cid:173)
`cally analyze, display and/or manipulate those ASTs. This
`method makes it possible to automatically construct systems
`for reverse engineering source code in any of a plurality of
`languages and for analyzing, manipulating and/or convert(cid:173)
`ing such code. This method also makes it possible to display
`and edit information as text in compressed ASTs in human
`understandable, pre-specified form.
`
`5,262,761 11/1993 Scandura eta!. .
`1!1996 Sotani ..................................... 395/703
`5,481,711
`
`10 Claims, 13 Drawing Sheets
`
`Flexform Structure ('.lbl)
`
`Source Language: java
`
`f3
`
`flexform Types
`
`Sections in Flexform Type
`
`Procedural Refinements
`
`class
`interface
`system file
`
`RETURN TYPE
`PARAMETER
`DECLARATIONS
`
`Add I Edit
`
`Delete I
`
`Add I Edit I Delete I
`
`i;i Includes PROCEDURE
`1;1 Includes Return Type
`
`Define Target Mappings
`
`Comment Delimiters
`
`Start: 1//
`
`IF
`SWITCH BREAK
`SWITCH(cid:173)
`ELSEIF
`WHILE
`FOR
`
`Add
`
`Edit
`
`_:j
`Delete I
`
`End: . - - - - - - - - - - -
`
`OK
`
`Cancel
`
`Add
`
`Edit
`
`Delete I
`
`FireEye - Exhibit 1021 Page 1
`
`

`
`U.S. Patent
`
`May 9, 2000
`
`Sheet 1 of 13
`
`6,061,513
`
`! · ............... · .......................... ·.···········································································································'•'•'•'•'•'•'•'•'•'•'•'•'•'•'•'•'•'•'•'•'•'•'•'•""•'•'•'•'•'•'•'•'1''' .. ''. ,. '. ,. '' .... '"''. 'll.,w.,.,~, .. ~., ·~"'"'"' ..
`,
`, ,,
`II
`
`::.,;·
`
`Rfi:cei\•<:< <;nd constrll!:t il S#t of prtl!fi'iJ.iOmhg :e:r:~):rnsnds sufficient l;,Jt cm;fit'tJtti(!Q il d~:;sire(:JI'temal r'.'lpr:BS•Bnt:ati·~·~· of sourc0
`as .:3t1 aMtrm;t syri!ti:<tteH in B?<~' -gi:ilfi:n iAngl>ii,;;:~
`
`"'"'"f·"'·!":r.~'·" emt,t:d•ment. ttl~·~ mprB·s0:-(~.:Jill)r; is ~~ C:Ciff!P{•:.:=5Beci eb:;-kact synt:'lK t'\?(l witl"l a~.r·•buh;~ ~n \r.;!-:k:h !::Kmi:::o:~ Of)rk>5
`., .. ,, .. "''''"''" iltt:h:!<3!3, in:.:t~·:i~=ng tl"1e CCinc:atsn~ted textual co11ror:ls o:' toi<Br:s lf: ssld q·a::r:r-nar, m1d ::n wNch ~:ut:kw.t> of sa:d nwie:;
`'•llilrc,··,m»"'"j stn.1c:1u:e:s .. 'Our:'h as ki::::G:5 o! pn;c:%Jura! r<::fimmw::t a:=>J ·d~:l<:l'"'ir::K:t:.n5 inherent n bJ t.:txlr.:
`lm:x•:"t a 8Nf g::ammar k;:: ;:1 gi~isr; ~r::Jgramming iangui3Ql3 ir:t:: :3 fonr'• Y>·here i::di,~ct\<::'1! ~-r•:;:d;;::jcr:o ca:1 be ef!sil:;'
`Th$ qKfent 0r::bod1ment Ll~$·; h<::d-:;tms
`~dent:ly constructs In the givBn l.B::::;;::Jag:;; !l'1at rr::c:·o:t he r~pws0nt~K! in ·cmd tfti\3 ae or!!:> Qi termif'=!3~ no=(h'i a:vJ wi:Ms% o! :x:~&s
`• rn~ i:1tern::li mpr;:;s!:':iliat:o:1, sorne o! whict1 ma;; h:w~? attribUi% ,..,hcJ~ am neMed :n c:c:nst(udin~! orr·1et noci8:e;. In tl·w
`:;;mMdim&nt th<::m r;n; Fle:<fnr:n mooul:>s \<J g .. b:::o~ion. dtib bloC:!() vitt·J tiitl and m;::w: ;:;:\kibultl5 ard two i~:i'i'''!:; ;;!'
`·st~C:tK1i1 ::"·;){:};. {$>-!J.! ~/6n'at:~:e. P::;}G6dUft;~). i;t:;j ;::::e{;~:~;f;-;lr~::! ::~~fin$}{!~3nt~:: (~.·~·; s::.~q:.Jence. Sel&r:;t:Qnj. ~3l~ij hje.r6ttJ:::cgl
`Tem1lna: ;;:lem6·:"ts :::Y•:sHu•kJ a !Qt.Jrh iwf.ll i.)!' c;::>rdn:c.:t h ih:B •p·=•sf~,,.,-,~:(j! ~m~:h>5~:r:::fi:f:l, t<:<rrn:n<ll ~J!<::i'fiE:ni:':.
`til<!>i t::<)f'rti:r: (;(lncat::mat-onf; of tf?4 $%\XI i;ll:,;;:j -~'llii'::
`:ncjhlidufal proGMUrfl ·>:M&n·:,:;.nts G!f" d:i~lit):'p8 rjec:I:Ji'f~ik:n~;
`•'IIIII•::=···'·~·=,,:,,, .. ," :~:::;!!;.i:ci3l tokens). r~-~:f! at:Gv:;. :::; a more p::$C!:se c:l:arf3•::ter:jz:e~or: of ~~nat ~r$ C$:;~~d· cor::p:~:~$6(:1 ab"S~ract sy.·::ta·{tr~e-s.
`· 0 s::r:gle ccn-siruct s•p$i1S or encorr:prii·:>~::rl mom tl'len onr3 production. men ~iie gmm6r rnav M cn~t0m:zed so thtlre is
`. one such producn-:::n. For ~wsrnple,
`
`F,;r eac:h of &::0 etw.;. ~sr::g::}Bge ,;:.~,~$lr>Jd~. id~.>ntiry t~KlSifl sp<E!ciBt rig!t ~1:an,:;; s~::l,;t,;:i;,'>:m> in spediic procJuctior:s in th=::> !)i;ren
`lai':guaga gram~1::1t lh::t corr:ilsp<:lnd &::• 0gtt·1 ~l~Jrt of i.htl ·:;(lf!~t.,.uct For eX:;J!nP,:e, a Vh~ie' !~J<:•p h:\=:1 fl'ii:l p,~r!~i, a :':lli':dil!on m:d ~l
`NOTE· Mer& tl:<!fi r;ne cord1u:) may C•'J(t::\S!)(:ncl b tne sarne prMuct:cr·:
`:n ~11:; CMfi. lo-wer ::ev<::~: tr:r,;;t::.:::;.:.s m:l::! be
`;sv8i con~~:ilJCls.
`
`option~~;~i:~:·~~:;~~~=~:c~1~!~;~. o~~~31~:t.uve tof(er1s ~~:,~~;:T~~~~,d~~J~~~~;~~:~~~ ~;;;,~:,;~~ 9 .r~~~c~~ :i~~B t~~~~,:y~,~~:~~~d
`c;;ns~u~nn:g non·ts;:rnina: r;:l)nstr:;(:'ts, om:tlB•::! bV.Bl'l'>. t•ect!ll1?. ;;utM:'J::l.a!!r:blJtes. Fe:· :nstar:<"''· :r: tt;:<;, pmd:.Kt:.c:n:
`
`· ri~~!:i M1d :>ids to:i;8ns Wf..J.:'i..E ~nd DO Wc(ik! t1e m:ited .:n [h$ ccnr::,~l:;t=:etion l>:,~ lht< k•nd t)! conotruct 0 tl., ;.NHLE \ix:'i:ti
`M· stortltl i;:: 11":•3 partmt 5<Jbtrl3e
`· • coro:rnands. t;) prodl.ldions in thG• recer-.•-ed grernrnar f.:::;: e:c,:<Gtn;ding r;,;n1pt%SB·:;: at•t;!ract ·s~nt:ax
`11111·-"'··o;,,!, ... o,,,.,, \'•ttl': fl:::.: t•or.stnJC!s !1peKi ~il~,j h:l>:::ve. Th:s sffip is tuiher :J)t;aborated in FigLr8 2
`!l:B n:::tt:lved grarrm·;<;:: a::x! ;:~tt::Jthed c1:<mmand$. Qii):;'1\1tate a ki1'19iJ~<ge
`pars,dr Wl':!d': !'I'Nt:m;:; engi!<l:):%fS s•c<.if·::?
`in that !angu::Jge 1nto cc<:11pr'<?.S~=M abstr;~d s;mlaxl:r&&·s.
`i!t:lhe pr~::!~ilt::t.' en:b:::::imr:~:::t, 8isQn !:, ;)sEJd to Qxn$t$_e ttlE'
`
`FireEye - Exhibit 1021 Page 2
`
`

`
`U.S. Patent
`
`May 9, 2000
`
`Sheet 2 of 13
`
`6,061,513
`
`ct.ion
`
`productions :n the recei\t&d grarnrnat for consvuc.t: ng
`i'\ssipn
`corr1pres:;ec1 abstmct syr-lh::!X trees, whdl are consish::mt ····.t~th th::l c:;:z:n::>tPucts
`· : &d:fie;~_i_r~_ff9_'~~-:;::_·! ~- __ " .. __ .. ______ . __ ................................................... .
`o:r:; s j n tl:f:i >w,:::;r-;·,.n·,
`the ne~<t production.
`custon~IZf:d c::o;'nrru:md ~:;as bee·n assi
`f<oer) n·:t::: cusb::nniZEHj comrnanri.
`Cr·eate a defat.J.It ce:mtnsnd ·,.~,t1.:~d1 n&turns t~·H~ concatenat: on cr
`throu~s-~ nr,;.·skd function call:;. F:::;;r
`r-i9r·1t (;and side
`oxnrnp!til, '·1 + :~ + 3' robJms th<::l con!.ont::;. oi u·n·ee rfQhi !:;anc~ s.;de
`on. For each acljaCi.':!nt pair
`kens in El
`tokens, i~' both
`.,~ .•... z,, .. ..,. corree.~pond to constructs {os sp(::(::fio{1 in Fi!Jun~ 1) tnen
`.~.-· •. ..-"''·"'•1'''""'·""'r'on r·eturns a r::evv parent nod~ ':::Vitll bctr: inpuit
`Otherwise .. c.or::catenation rE:tuny,:; <:?: nod<? :n v·.ft·li(:·h
`chi
`.• ib1..1tes of Um ':':;econd node E<re appended to the
`atlnbuh::.'s of the HnJ
`th•::. ::::::hddn,:n of thiJ
`.~ ... -.. ,.. .. , .. ,,.,-·onr.Ji
`thfl
`econd node arrl orJdocJ rdt:;,;:r u~:e c:.hi
`fetTed ernbodirnent. the n9su!tlng node
`{,,..·,j·-.,.<··~~,~··,::.r">,:;;r: on of h::xt in Vl•;;i t:;\:{:l nodE~S (see Detailed Description
`if a construct ls expii:cit!v a·s.sign•0d to right ~·:an:rj side tc:kens in
`s ;::wc,ducti on (th::ln':' nv.r/ t''"' n·l()i'f? u·1an one). tt"len insert a
`(!!l'!man,j
`creat1ng tl1at level •.:Jf ... ::;(>nsrrucL
`c:ornrnand.s
`ana :')IYll>?,cidE!•d 1n the otdt~r of k<~st to rno:st e·nc·ornp6::rss~ll9
`constnJcJ
`In the prof erred ernboctment, the: const:·ucts are.
`nai elernrmts {n:f.l(io~n. procedural n:;,f!nr;;.:rr1ents and
`h:erewchlcal data stt·uctures.
`on roots a:·1d Fexfon-rl rnodules. ·
`(.~r sr•ec.::ified <.c::stt'lbt~to:::
`riQht hand ·;;ide inciudoE '<idE->nt:
`rmefJed :n cons1nJ:c.:t!:lg ot!ler
`(e g , narnin9 Flexforrns }. a
`te:tnporary ;:Jlt:·iL!ute is :s:tomc1 in u-·1t: output of ths~; flt"<J:::luc:bc,n
`VV!:,en Cf\'Jdtinr;:~ a terminal node; thfl ts,mporary sttri:bute
`lS rE:ltriOV&ti !rom ternpor;:H·y· stst:.Js and pt:rrnN.i<:=:nt!~-l
`stonad in thE? n:::.mw ,,~ttnbute.
`· . ; , r:; construeti ng .a :::ubtree no(je, the, temporarv <attribuh:::=:: c"Wf'
`lr1 trv:o
`P:?n:o'.:txi !'rotn tmnpon:lry ~.tatus ancl p.;:;rman:s,r:tly ston::::d
`prefern·::d ernbodirnent, l'or exmnp~e. the Fk;ixJorrr: r-·:;.3t'{i':J is stcred
`in tho Flox.form me na:T18 ettrfi)t . .lhs;.
`
`FireEye - Exhibit 1021 Page 3
`
`

`
`U.S. Patent
`
`May 9, 2000
`
`Sheet 3 of 13
`
`6,061,513
`
`_ ~~'?~··~l r~1.~~t:~~~(:l~ ~t ~(l!~~,:-~CY: [PT_c:~::~9-~~~~lJ! _______________________ _
`::::.] nr~•rn•-r·~:·r· <~r····j(-.1 ~q·~fi ('':::.~ >.Aflql','7i;!!- f.---~~--
`::;, f"'l\IC>l-1 n::!-nl-!!-Of"Plll·· I. :nl-!
`... J .. \...:?-·A vC~f: ·f~~
`r:·-· ·•
`•. /I
`~;j·~ J_.~., t !~ :. ~U.· U
`.... ~ ..:;.,-!
`{.:~ _'! ~ ....
`.::J~ '.!c.._..-..
`{.:J!- ~ t
`-~ .. -~
`-.,....,
`:! Q,_,..
`·· ... .:}
`or dialect, and an assoc::iatecJ language independent
`0 1 wp ·j
`··::.<tl:d. C(·,~-~c·t-r·t 1 t~t<:· C:P.!FF·:t'(8j ;[~I gC·f'CI~-,-j•::jtl· CP ~·~>lt''
`C:~t-·
`V~:-:.:.J·:I_~~._...J.~ .... ·._.·
`.... ~• ... ·.·.v,
`~
`V..:.•~ ....... t .... ~_,.A_~· . .A·
`~(~~---!·l
`~0:.-.A~'-<'
`.1
`for.· ,-···or•cf:rU· c:ti~ln ··:::> c·~o~-r1 niAt"qAr't.:'-l•-v h-·:::<jj:d :(~r-C<n'">f"P·.A~- t'r'ir·
`!~~~~ .. _.. ~·.·J·.9,•._.-.f,..-, 3tc{
`·-:::.~ u~~t .. ~r..=..~·~
`-:t ~ o
`......
`:,__._,
`~., ......
`~-;.; ....
`~ ......
`-
`.
`manioulatino terrnina!""lt::lvoi c:or··IGtruc:ts in u~1G
`nQ
`c:c:rrespondi n9 cornpre':ssed f.itYstract s~/ntax tree for- the gh.N3'n
`
`1
`
`(.-.
`
`'.:C::
`0:. .• :~
`
`'-~"'y.':;
`
`·..,.!.
`
`~
`
`!_._.-!
`
`·: ~ •··• .. Af :·
`
`3.__.:.
`
`:;; _ _,.:
`
`... ...,:.
`
`.! •-..
`
`•• .,.e
`
`:•
`
`.._ •. '
`
`I (l··--::·~.~-,1· :f.: , t'~·-, .. , ("jn.·~l· ~-J~ l.(P.tl ("• f t·l-'-'·<~ ('<rr.~~-·(l:''''i:c::ir"·
`::.:> F··l ·:~ i··:,f-t }···,;::li""""::d C:l"(b-
`'i l!"·"ll. c···-~···,.
`! -~~·: H,· ;: J .:: ::t:?" ~j--:J-·~. ~~ ~ ·~-.....-~ "
`· .... '. .: Sv :y cH !:
`1t\
`·t !:
`::.I
`~ ~-... A~ ·:
`~·v·
`-: .,_'t
`token of the top production. R:ernov·e all productions vvhJOSEl !oft
`hand side is this ~}CH:3t token.
`'.FC';1' A··;r<h (':"lrl:r::t:n ICt t:<n(J 6 ~,,~.h tJ' ~-o::j:; j(~hr1n r····ol·~,f,~-.,l·r·-lit''f·~ -::;H::·s··:g·· r·J8<'~
`W3 ~ J v·:CA ,.,.. i .! t 1
`.. (,,A
`.. l
`..... *'·Co;".d·: ~
`-~.......
`·' • ..... " ...._, ,J..,· ·-· ~ •.
`~oc.L~
`~
`f~:-;.1 C~-·J
`~
`..
`'
`ri 9ht rlarld si cle tokens for- that con:;truct introduce a nEN>J'
`prcdudi()n Thi~; pmduction rlas the ori~Jinal D08i token on the !eft
`hand side. Tr1e first l'igtlt hand siide token is a fn:;;ud token for the
`constnJot (e.:;J., 'fraucJ~rf~conctitlon' for tt-le condition part of the if
`tokens i rnmedi atelv
`c=onstruct). Tile a~;~:i ~jnecl n t~mt hami
`fol!o~N the fn::nJd tok-.:m.
`D!.:;:::~~:~ .. ~~~ ,l?_~?~!~t_e: J:,t~:~l-~--~i:::r.~ . .r?~~.~ . .i!~ _.9~~~~r:r!~::~~--~- _'" :c~ .. ~l.:~~:.-.. ~~"~~1 ~:, , .. _ .......
`~~·onc::kl::r-J c:. <.::·1 J'f""'l·"'~"~,i nf t>-,.o ']·r-·:':>rrlnlPr 1. ''' rnt J~t~n~l"' k-"he~od
`J ~ ~~-~
`:::_ · (.:.!
`............ : !· ~I ' .. C.J ~ J
`'.·:·
`..., 3 ,-_;. .,_~
`diroctod grapty1s (vvt1ere each left hand ~;ide toi<J3n points to its
`correspcwKll ng d ~Jht t·1and ·;!de tokem:::), s!1cn.Ni nQ t1ovv ri gr1t r-1ancJ
`side tok.er;s are denve::.::l fn:J:rTI ls~ft t!i:md Slcle to~;:en:;. !n :;ucr-1
`nr'fW)lS" Pl. 1'1. r1[-!t ~,'l;;Jnd sicjr> rr18'·i tlA rjer·:\/A(j ft"YWn b.vr·, 1'>"'1 .. n::n!'A fc;,ft
`,::1
`hartd sides, and 21 tok~?Jn may dt rect!y or ! n:di rectly denve itse,lf
`(. i (;-,
`c··,v::-'h~ \
`.. ,v~~ ~,~ ,...,.,,_.,.(·
`
`...._~ ._, ·
`
`._,. ~.J
`
`o: .._, .. ~ ~:.~
`
`.
`
`·•
`
`,.
`
`,_·_<
`
`~ ••
`
`~
`
`, •. •
`
`••
`
`.•. ~.) '-."./
`
`•l"~J "'-~
`
`:;!}
`
`:;.:A~·~
`
`~'
`
`',o..
`
`<
`
`'"--'- '
`
`~ c_o;
`
`~
`
`•_.'
`
`:
`
`,0
`
`)
`
`-
`
`•../
`
`....
`
`'·~ ,l
`
`'•
`
`...,,,,
`
`•'
`
`'-'-' ~
`
`... (
`
`0
`
`......
`
`......
`
`l ~ •! 'J.'
`
`. / '' ...... ~ '-"•
`
`FireEye - Exhibit 1021 Page 4
`
`

`
`U.S. Patent
`
`May 9, 2000
`
`Sheet 4 of 13
`
`6,061,513
`
`Figure 4.
`
`::;,,~ L4:
`
`~ •.I
`
`·: :Q., ~A~ ~
`
`~!. ~.
`
`J
`
`~ -J~ ..... ,,:
`
`.~-:. ~ •.Co . .... ~
`
`t
`
`·'-'···(A!·~~
`
`~;_,~
`
`~ ~ ~!,_:;.:
`
`l t\_,c,,.,. '¥.•':....J
`
`,~ .. ?.~r.~~J: ~~:t_t~~s:~q .. ,.,./~ ;_[]!i_~~~9:ry _;.( t~J~_:?':;~(~!·J.r:~J: . _. _. ______ ~ _ ~ ___________ _
`(;p./en a compresfH§<j at~strac:t s;yntax tree ~·v1th attributes constructed
`in accorcLenee wiHl the mett1od of Fi~Juro ·1. ancl a lexica! anaiyD3r.
`lan1guagt-s: lnd9pGnch::;rlt parsot-, and fraLJd ~warnrnm· c:onstnJcted ~n
`accordance witt: the method of Fi{)Um 3. ·a rnethod hx analvz!
`and
`convertin~1 at least cme of: (a) :::>aid terrntnc.ll nodes
`d fraucJ
`ng
`'"'"0" r··r··.;nf"A':··cAd tt~AO )''1+-::.nr-A' n· 0:::: ·-::<' rj t,:::,,·m~ .-,.::::;1: n-:""'<(j.0>C::
`,...1· ;···.;;;,ry·W'"''-""f •;;:;n,cJ n.)- \ Cc:::>I·"-J
`.;::·J,:J . ._J v
`· ··t: ~ \,_.. . .:;) . .J ._..,
`i nl?~L}~!~ _ ~::! J~ ~ £· .. = .. ~~~t-~t~r~~!~~~ ,_ -~?'_:.?!:~~?!:~ ~)r:~~): .... __ . _, _, _, _. _. __ ~ .. __________ _
`a)" f:~r~~:;,t~-~l:~~ -~t~~~~"~ _ 9!~~r~r:~~~~-~r: R~:~~~t?!~ __ ~~=~- ~-r~~~r:~~l- ?:~~:~! ~: ............. _ ..... .
`. Attach cornmands to productions in the Diven! fraud grarnrn~3r·.
`VV!·-!enever information denved from a pn:"::lductiCWI vvHi De neececl
`h•\; C-> r:nrntllD''-Id _..,tt~'"'hAd h'!· (J' t'lA !.J-·t- rn.---trA cuhC'e·qUPr-lt r··t<""(!(j:: :V'.ti ('f":C'
`~ J. !·::S,
`:-...---::>
`........
`f-" 3 ,_. ·- -•.AV
`stor·e rlght hand sido tokens as attributes in the output of th:e
`~'r·-l·~d~· Jf··t·l r·1n
`\fV!lere r~pproprlate, ciets~rmine vvhat r;omrnands to attach to gb;en
`u-·Je given fraud grarTHT1ar
`produc:ti
`on U·H~ above said
`.Cltt: r; hLlfP ,,~~
`
`'"~·-• . / r-:. . ..&
`
`./ ~_,.,,
`
`j ~~:
`
`~..-(J
`
`.,..,..,
`
`'.."..~
`
`'C.<'~J
`
`"'""'
`
`.
`
`.t.·~~
`
`*..-
`
`I
`
`v
`
`'
`
`., .~ .... - ~ ~ ......... ~
`
`~·
`
`:!'-"~
`
`·7 • .... ~ -·- ........ •
`
`·, .... !·
`
`•' '
`
`• ... 0:0!--·'
`
`'•O'o<:
`
`,.,:;.,?•...-,
`
`(, , ,A\
`
`)
`
`"•.•.•''
`
`,
`
`• ".;,/'' •
`
`, •
`
`' - ' ~ ~ • ._.!•
`
`.. '
`
`•
`
`......
`
`r--~ E '•
`
`•'"'-' •./ '
`
`, ~ ·,--•
`
`~
`
`; j
`
`::;. t,•
`
`h
`
`' y'
`
`... ,...... c,..-~
`
`•:
`
`('" onctrud '"'O .... ie Whi t'·rl ar·1~)lb~c di rpcl-1'· '' to ni'"·tfi8S 8f'""irl .~l·r; wtur.::;,c:·
`{ h '!
`i. j
`·~· .......
`'"-"
`in safd c.ornnre:ssed abstract svnta:x tmo
`! n the preferred
`!'""
`..
`.
`c·~ ~Qh: (':~·:j;:::. t'll":·PratAc Or" trlp r·:0tllpp:~ccf~d-. h·ee· . ( q: \
`A~'>"""::f)(~l«ll' vflf';tlt
`.. ; . . J ~
`_,.,,
`··: ·-)~ ...
`( '·
`".:;. 1,.,.\'/
`·-1 <-·:v·..-:1'· . . -.-;-.~-"v.:
`-..Jl ~ ~.,;_._
`<t""(·l-;--f···]At"i~'""tAi'U t"IC>f'nt·c,, -;.:;nst r .. orr]1TI"'<ri({ ··:-:ltt·· .c:l(":~'Rf"i fn ""' r·~n~iC)i i(:ti·Qn 1.0::::
`.) C:.~lo. "O..o.:'! •.•' ~ 3 Z•.•
`.,"'" .. '·l ./ v
`...... t ....... <:.I !._.")
`~
`..._,. 'J.~ C<
`• -~ ~
`c.:~
`~--· •'
`~-
`....... '-~
`._,.
`t
`..... ~· .. j .·~ft-:8"" tf·· .... '~ -.. ·"~ ., ..... ,~, -""~ .~. h
`l--. , .. f·--·
`. .-.! > >···'
`.-•• ·"·h " · ' ,!-
`F······:~,~ ,.f
`,~, ... -. '·~
`''V'i.:::l\...-·1 I
`':;:::'\.~ ors!! o! t;•
`t-;..:< .. tl<..-Ln6u' :. u} Ut.! l,)ro al :!1 • .,1 0 :_
`j lH I IU\,l'S!~::_, 1:: i
`:;
`pr-c~c~;:ssed, ancl ( c} art or- aU commanc1s attact'leKJ to e product: on
`
`·.__;~'.,:.,•
`
`v'
`
`~
`
`~
`
`.,...
`
`""~· .. ),
`
`...... ~:;;>..._!··---·
`
`'J..,
`
`._ ....
`
`·!· • •. >
`
`{.-::
`
`•• , ...
`
`'"'· ..
`
`·'-'•'
`
`FireEye - Exhibit 1021 Page 5
`
`

`
`U.S. Patent
`
`May 9, 2000
`
`Sheet 5 of 13
`
`6,061,513
`
`Figure 5.
`
`...
`
`Grammar Productions
`
`Literal·> INT LITERAL
`Literal·> STRiNG LITERAL
`Literal·> CHARACTER LITERAL
`Literal·> LONG LITERAL
`Literal·> FLOAT LITERAL
`Literal·> DOUBLE LITERAL
`Literal·> TRUE TOKEN
`Literal·> FALS( TOKEN
`Literal·> NULL TOKEN
`Type·> Primitive Type
`Type·> Reference Type
`Primitive Type·> BOOLEAN
`Primitive Type·> Numeric Type
`Numeric Type·> lntegrallype
`Numeric Type · > FloatingPoint Type
`lntegraiType ·>BYTE
`lntegraiType ·>SHORT
`
`A_gcept
`
`Cancel
`
`FireEye - Exhibit 1021 Page 6
`
`

`
`U.S. Patent
`
`May 9, 2000
`
`Sheet 6 of 13
`
`6,061,513
`
`Figure 6.
`
`~
`:!:::,utoBuilder ~imulate §enerate Reverse engineer/import
`Eile Edit
`],anguage Tools Tytor
`Auto~uilder Tools
`
`~~
`Iranslate RepQrt/export
`
`- _j
`
`_j Fle~form Definition
`_j Grammars
`_j Le~ical Analyzers
`_j Generators
`
`c: \temp\J ava.lang
`
`Java_Language
`
`System File
`r
`
`Suggested Next Achon
`
`t3
`
`You must import a text file containing a full grammar [i.e .• for files) for this
`language into a Fle~form. (This is a full grammar as opposed to a partial
`grammar used to parse individual Flexform nodes. J The next dialog lets you
`do this automatically.
`
`_j
`
`Cancel
`
`FireEye - Exhibit 1021 Page 7
`
`

`
`U.S. Patent
`
`May 9, 2000
`
`Sheet 7 of 13
`
`6,061,513
`
`Lex1cal Categories and Patterns lor Teuninal Tokens 1n Language
`
`Sub·Pattern: Pattern
`
`Category: Pattern(s)
`
`Keywords
`
`Figure 7.
`
`l3
`
`HEXDIGIT: [A-Fa-f0·9)
`OCTDIGIT
`[0-7)
`DECNUMBER: [1·9]{DIGIT}'
`HEXNUMBER: O[Xx){HEXDIGIT
`OCTNUMBER O{OCTDIGIT}'
`DECLONG: {DECNUMBER}[LI]
`HEXLONG: {HEXNUMBER}[LI]
`OCTLONG: {OCTNUMBER}[LI]
`EXPONENT
`[Ee][+-]?{DIGIT)+
`FLOAT BASE ((({DIGIT}+\ {DIG I
`
`Add
`
`Edit I Delete
`
`NOTE: Sub-patterns are used to
`define patterns.
`
`"//".'
`
`\'\~
`
`\<\<
`
`\>\>
`\>\>\>
`
`<comment 2>:
`INCR:
`-
`\+\+
`MUL EQUALS:
`DECR:
`\-\·
`SHIFT LEFT:
`BITSHlFT RIGHT
`FILL SHIFT RIGHT:
`LTEQ:
`-\<\=
`\>\~
`GTEQ:
`EQUAL COMPARE:
`NOT EQUAL:
`\&\&
`... t
`AND:-
`\l\1
`OR
`-=...J
`6dd Comment I .!;_dit I Qelete I
`NOTE: The syntax checker & converter
`assume that <identifier>, <comment> and
`<white-space> are declared.
`
`\=\=
`
`\1\=
`
`)
`.=::J
`
`<···_I
`..::.::J
`
`PACKAGE
`BOOLEAN
`BYTE
`FLOAT
`SHORT
`INT
`LONG
`CHAR
`DOUBLE
`IMPORT
`CLASS
`INTERFACE
`PUBLIC
`PROTECTED
`ooniATC
`l;i" Treat UPPER asjower case
`
`NOTE: <eof> is automatically
`returned at end of input.
`
`I
`
`!gnore Case
`
`Number of Lookahead Tokens: ro--
`
`!Jpdate this Lexical Analyzer from Grammars
`
`Done
`
`Cancel
`
`FireEye - Exhibit 1021 Page 8
`
`

`
`U.S. Patent
`
`May 9, 2000
`
`Sheet 8 of 13
`
`6,061,513
`
`Flexform Structure(' lbl)
`
`Source Language: java
`
`Elexform Types
`
`Sections in Flexform Type
`
`class
`interface
`system file
`
`Define Target Mappings
`
`RETURN TYPE
`PARAMETER
`DECLARATIONS
`~~Delete!
`~ Includes PROCEDURE
`~ Includes Return Type
`
`Comment Delimiters
`Start 1//
`End: r - - - - - - - -
`
`Figure 8.
`
`EJ
`
`Procedural Refinements
`E:LDCt
`IF
`SWITCH BREAK
`SWITCH(cid:173)
`ELSEIF
`WHILE
`_
`1
`FOR
`.....:J
`~~Delete!
`
`OK
`
`Cancel
`
`FireEye - Exhibit 1021 Page 9
`
`

`
`U.S. Patent
`
`May 9, 2000
`
`Sheet 9 of 13
`
`6,061,513
`
`Figure 9.
`
`13
`
`•
`
`~
`
`Correspondence between tava Constructs and Grammar Productions
`.2.ections
`flexform Types
`
`tut1(.t10t1
`class
`interface
`system file
`
`Assign Productions to:
`
`Flexform I
`
`Name I
`I okens to 0 mit
`
`RETURN TYPE
`PARAMETER
`DECLARATIONS
`INCLUDED FILE
`INHERITED CLASS
`Assign Productions to:
`Section
`
`I
`
`r
`
`~ Delete!
`Assign Productions I
`
`.Erocedural Refinements
`BLOCK
`
`•
`
`SWITCH BREAK
`SWITCH=BREAK- alternative
`SWITCH
`SWITCH · alternative
`Assign Productions to:
`Refinements
`
`~
`I
`
`Element
`
`Edit §rammar
`
`QK
`
`b;ancel
`
`FireEye - Exhibit 1021 Page 10
`
`

`
`U.S. Patent
`
`May 9, 2000
`
`Sheet 10 of 13
`
`6,061,513
`
`Figure 10.
`
`Assign Productions to IF R ehnement
`Grammar Productions
`
`EJ
`
`Unit File-> Goal
`GoaT-> CompilationUnit
`Literal-> INT LITERAL
`Literal-> STRiNG LITERAL
`Literal-> CHARACTER LITERAL
`I it"'r""l -'> I nNr:; I ITI=J:l61
`8ssign Production
`
`Assigned Productions
`
`lfThenEiseStatement ->IF'(' E~<pression ')' StatementNoShortlf ELSE Stat!
`lfThenEiseStatementNoShortlf -> IF'(' El<pression ')' StatementNoShortlf E
`
`f:.dit
`
`Qelete I
`
`lfThenStatement ->
`Construct Part
`r. Cond(ition)
`r- Then
`r- Else
`r- Omit 11:;~<~<)
`
`Part
`:-::-::-:
`Cond
`Cond
`Cond
`Then
`
`Right Side Tokens
`Click on right side token
`IF
`for current construct part.
`'('
`E~<pression
`')'
`Statement
`
`.QK
`
`Cancel
`
`FireEye - Exhibit 1021 Page 11
`
`

`
`U.S. Patent
`
`May 9, 2000
`
`Sheet 11 of 13
`
`6,061,513
`
`Figure 11.
`
`1!!1~ E
`Cop~right 1997 ScandYra ~
`
`iii View/Edit Flexform
`[java.s~nl:S~ntaH
`GraMMar for reverse-engineering FleHforMs.
`Note that all graMMar nodes below MYSt be grandchildren of this root node, and __j
`that each grandchild MYSt contain a separate prodYction grouping (with the
`coMMands for each prodYction in separate nodes beneath the corresponding
`nonterMinall.
`\ · araMMar: · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · • · ·
`I
`Pseudo..,.Goal
`siMple stateMent siMple stateMent definition <eof>
`-> Trau
`case_stateMent case~stateMent~def1nition <eof>
`-> fraY
`if condition if_oonoitio~defLnition <eof>
`-> fraY
`for control for_oontrol_oefinition <eof>
`-> fraY
`-> fraY
`whiTe_condition while_condition_definition <eof>
`until_condition until1condition~definition <eof>
`-> frau
`case selector case se ector defLnition <eof>
`-> fraY
`-> fraY
`SWifr~1 SWITC~l_oefinition <eof>
`SWITC 2 SWITC Z:definition <eof>
`-> frau
`SWITC 3 SWITC 3 definition <eof>
`-> frau
`-> fraY
`ELSEI
`1 ELSEI~l:definition <eof>
`ELSEIF":'2 ELSEI~_z=definition <eof>
`-> frau
`ELSEI~3 ELSEI~3~definition <eof>
`-> frau
`TRY 1 TRY 1 defTnLtion <eof>
`-> fraY
`TRY:2 TR~Z:definition <eof>
`-> frau
`TRY:3 TRY_3 definition <eof>
`-> frau
`REfORN_TYrE:value RETUR~YPE_value definition (eof)
`-> fraY
`PRRRMETE value PRRRMET
`value_defTnition <eof>
`-> fraY
`DECLRRRT~NS value DECLRR TIONS[value_definition <eof>
`-> fraY
`INCLUDED FIL~ value INCLUDED Fl E_value_definition <eof>
`-> frau
`INHERITEO_CL~~S~value INHERITED1C~RS~value definition <eof>
`-> frau
`INHERITED INTER~RCES INHERITED NTER~HCES definition <eof>
`-> frau
`CLRSS DEC[RRRTIONS CLRSS DECLR~RTIONS definition <eof>
`-> fraY
`INTERFRCE_DECLRRRTIONS I~TERFRCE_DECL~RRTIONS_definition <eof>
`-> frau
`siMple stateMent_definition
`->THROW EHpression '•'
`->RETURN EH~ression 1 ~·
`-> RETURN '~
`->CONTINUE Identifier·~·
`-> CONTINUE '·'
`-> BRERK Identifier·~·
`-> BRERK '•'
`-> StateMentEHpression ·~·
`-> •.•
`-> S~PER '(' OptRrguMentList 'l' '•'
`-> THIS ' (' OptRrgYMentList 'l' '~I
`OMMands: Rrrows,AH,Ag,1 •. 9,+,f,n,b,r,Del,t,M,d,c,a,e,s,Af, l,w,g,p,?,Help=Fl,E6c~
`
`FireEye - Exhibit 1021 Page 12
`
`

`
`U.S. Patent
`
`May 9, 2000
`
`Sheet 12 of 13
`
`6,061,513
`
`Figure 12.
`
`£i
`
`Create New Code Generator
`
`J . . 3
`Is 3
`f72 3
`17 3
`172 3
`
`[indent_per_level]: number of spaces to indent per level
`
`[start_ comment_ column): column where comments
`should start [e.g., 6 for COBOL]
`[end_comment_column]: column where comments
`should end [e.g., 72 for COBOL]
`[start_code_column]: column where code should start
`[e.g, 7 for COBOL)
`[end_ code_ column): column where code should end
`[e.g., 72 for COBOL]
`
`OK
`
`)
`
`Cancel
`
`FireEye - Exhibit 1021 Page 13
`
`

`
`U.S. Patent
`
`May 9, 2000
`
`Sheet 13 of 13
`
`6,061,513
`
`Figure 13.
`
`1!!!11!1.
`
`_j
`
`ii View/Edit Flexform
`-> frauc~~WITC~l SWITC~l_definition <eof>
`-> frauc~~WITC 2 SWITC Z:definition <eof>
`-> frauc SWITC 3 SWITC 3_definition <eof>
`-> frauc~~LSEI~l ELSEI~l_definition <eof>
`-> frauc ELSEir_2 ELSEir_Z:definition <eof>
`-> frauc ELSEIF:T3 ELSEI~3~definition <eof>
`-> frauc TR~,1 R~,1_defLnLtion <eof>
`- > frauc TR..-_2 TR..-_Z:def in it ion <eof >
`-> frauc TRY:3 TRY:3 definition <eof>
`-> frauc_~ETURN_TYPE:value RETUR~YPE_value~definition <eof>
`-> frauc PRRRMETE value PRRRMET
`value_defLnition <eof>
`-> frauc:~ECLRRRT~NS value DECLRR TIONS[value_definition <eof>
`-> frauc
`INCLUDED FILE: value INCLUDED FI E_value definition <eof>
`-> frauc:~NHERITE'O_CLRSS!"value INHERITEDTC[RS~value definition <eof>
`- > frauc -,INHERITED[INTERrRCES INHERITED15 NTERrHCES definition <eof >
`-> frauc CLRSS DEC RRRTIONS CLRSS DECLRnRTIONS definition <eof>
`-> frauc:INTERrRCE_DECLRRRTIONS I~TERFRCE_DECL~RRTIONS_definition <eof>
`.. S'iMDle· ~tate~~~t. deft~ lt l~~ .......................................... :
`->THROW Expression
`•
`-> RETURN Expression
`,
`-> RETURN
`->CONTINUE Identifier
`-> CONTINUE
`-> BRERK Identifier
`-> BRERK
`-> State~entExpression
`->SUPER'(' OptRrgu~entList 'l'
`->THIS'(' OptRrguMentList 'l'
`I 1 + 2
`1 + 2
`1
`1 + 2
`1
`1 + 2
`1
`1
`1 + 2 + 3 + 4
`1 + 2 + 3 + 4
`OMMands: Rrrows,Ax,Ag,1 .. 9,+,f,n,b,r,Del,t,M,d,c,a,e,s,Af, l,w,g,p,?,Help=F1.~c~
`
`FireEye - Exhibit 1021 Page 14
`
`

`
`6,061,513
`
`1
`AUTOMATED METHODS FOR
`CONSTRUCTING lANGUAGE SPECIFIC
`SYSTEMS FOR REVERSE ENGINEERING
`SOURCE CODE INTO ABSTRACT SYNTAX
`TREES WITH ATTRIBUTES IN A FORM
`THAT CAN MORE EASILY BE DISPlAYED,
`UNDERSTOOD AND/OR MODIFIED
`
`2
`analyzers, which identify structural characteristics of the
`source code. These characteristics may range from the
`highest (e.g., program) level of abstraction inherent in a file
`to the lowest level tokens (items which make up individual
`5 expressions). In this case information is stored in what are
`commonly called abstract syntax trees (ASTs), in which
`individual nodes may have various attributes. For example,
`a variable may have type and/or value attributes.
`ASTs themselves are typically constructed by attaching
`10 small routines or code fragments (hereafter commands) to
`individual productions in the grammar, which work in
`conjunction with a language independent parser.
`Specifically, a programmer or parser generation program
`(e.g., YACC) attaches commands to individual productions
`15 in the associated grammar, which convert code as it is being
`parsed into an AST.
`The process of constructing standard ASTs from given
`source code using a grammar representing the language in
`which the source code is written is well known (e.g., Aho,
`Sethi & Ullman, 1986). Parsing source code into trees plays
`a major role in analyzing and/or transforming that text. A
`variety of techniques have been used to improve the process
`of compiling source code. Carroll et al (U.S. Pat. No.
`5,812,853), for example, revealed an improved form of
`prefix analysis to speed the process. Parsing techniques have
`also been used to analyze and/or translate natural language
`text. Kuno et al (U.S. Pat. No. 5,528,491), for example,
`propose a system that allows human operators to interact
`with automated translation processes in a way that preserves
`correct portions of the translation. Success in attaching
`semantic information to ASTs for reverse engineering pur(cid:173)
`poses and/or to facilitate program understanding also has
`been achieved (e.g., Canfor, Cimitile & Munro, 1993; Welty,
`1997).
`Although the process itself is well known and widely
`used, creating reverse engineering systems that can auto(cid:173)
`matically constructASTs from source code takes a good deal
`of manual effort. The more constraints on, or special char-
`40 acteristics an AST is to have, the more effort that is required.
`Knowing which commands (or routines) to attach to
`which productions to construct particular types of ASTs is
`not an easy task. It requires intimate familiarity with the
`grammar, the goal to be achieved (e.g., the type of AST) as
`45 well as the programming language used. For example, it is
`relatively easy to construct ASTs from source code where all
`constructs in the language are handled in a uniform manner.
`That is when everything from atomic tokens in the language
`to high level constructs (e.g., procedural refinements, rela-
`50 tions between modules, units, etc.) are to be represented as
`nodes in ASTs in the same manner.
`Attaching commands to individual productions in a gram(cid:173)
`mar to achieve prescribed puposes is complicated. Adding
`semantic attributes to, or constraints on, the to-be-
`55 constructed ASTs further complicates the process. Achiev(cid:173)
`ing any specific goal, whether it is to construct a particular
`kind of AST from source code, or to manipulate text using
`a grammar requires attention to all such commands and the
`grammatical context in which they are executed. In
`60 particular, commands attached to any one production must
`take into account commands attached to other productions,
`which will be executed when the source code is parsed. In
`addition, attributes derived by manipulating tokens associ(cid:173)
`ated with any one production may effect what manipulations
`65 are to be performed by other productions. Complications
`deriving from such context dependencies increase rapidly
`both with the number of dependencies and the length of the
`
`CROSS-REFERENCE TO RELATED
`APPLICATIONS
`Aho, Alfred V., Sethi, Ratvi and Ullman, Jeffery D. Com(cid:173)
`pilers: Principles, Techniques, and Tools. Addison(cid:173)
`Wesley: Reading, Mass., 1986.
`Canfor, G., Cimitile A., and Munro, M.A Reverse Engineer(cid:173)
`ing Method for Identifying Reusable Abstract Data Types.
`IEEE, 3, 1993.
`Scandura., J. M. A cognitive approach to software develop(cid:173)
`ment: The PRODOC environment and associated meth(cid:173)
`odology. Journal of Pascal, Ada & Modula-2, 6, 1987.
`Scandura., J. M. Cognitive approach to systems engineering 20
`and re-engineering: integrating new designs with old
`systems. Journal of Software Maintenance, 1990, 2,
`145-156,
`Scandura., J. M. A cognitive approach to software develop(cid:173)
`ment: The PRODOC environment and associated meth- 25
`odology. In D. Partridge (Ed.): Artificial Intelligence and
`Software Engineering. Norwood, N.J.: Ablex Pub., 1991,
`Chapter 5, pp. 115-138.
`Scandura., J. M. Cognitive technology and the PRODOC
`re/NuSys Workbench(tm): a technical overview. Journal 30
`of Structural Learning and Intelligent Systems, 1992, 11,
`pp. 89-126.
`Scandura., J. M. Automating renewal and conversion of
`legacy code into ada: A cognitive approach. IEEE
`Computer, 1994, April, 55-61.
`Welty, Chistopher A Augmenting Abstract Syntax Trees for
`Program Understanding. IEEE, 1, 1997.
`
`35
`
`STATEMENT REGARDING FEDERALLY
`SPONSORED RESEARCH OR DEVELOPMENT
`
`Not Applicable
`
`REFERENCE TO A MICROFICHE APPENDIX
`
`Not Applicable
`
`BACKGROUND OF THE INVENTION
`
`Understanding and maintaining source code is largely a
`manual process. A human must study the code to understand
`what it is doing and must make desired changes to the code
`manually in a text editor. To help automate some of the more
`common and onerous tasks a variety of text editors have
`been constructed to analyze and manipulate text files con(cid:173)
`taining source code. Many of these editors are based on tools
`such as grep, awk and their derivatives for analyzing regular
`expressions. Such editors help in detecting patterns and
`often make provision for automatically changing the code.
`Text-based tools work reasonably well with easily identified
`text groupings (e.g., text on one or more lines) but they fail
`to adequately address structural characteristics of the code.
`It is not feasible, or in many cases even possible to detect
`complex structural patterns in the code, much less to make
`desired changes.
`The current state of the art is based on repository
`technology, in which code is typically reverse engineered
`into abstract syntax trees. Reverse engineering technologies
`are based on grammar-based parsers and associated lexical
`
`FireEye - Exhibit 1021 Page 15
`
`

`
`6,061,513
`
`20
`
`3
`grammar. Cyclic relationships in grammars furthe