static single assignment for decompilation

Lesson 6: Static Single Assignment

• discussion thread
• static single assignment
• SSA slides from Todd Mowry at CMU another presentation of the pseudocode for various algorithms herein
• Revisiting Out-of-SSA Translation for Correctness, Code Quality, and Efficiency by Boissinot on more sophisticated was to translate out of SSA form
• tasks due March 8

You have undoubtedly noticed by now that many of the annoying problems in implementing analyses & optimizations stem from variable name conflicts. Wouldn’t it be nice if every assignment in a program used a unique variable name? Of course, people don’t write programs that way, so we’re out of luck. Right?

Wrong! Many compilers convert programs into static single assignment (SSA) form, which does exactly what it says: it ensures that, globally, every variable has exactly one static assignment location. (Of course, that statement might be executed multiple times, which is why it’s not dynamic single assignment.) In Bril terms, we convert a program like this:

Into a program like this, by renaming all the variables:

Of course, things will get a little more complicated when there is control flow. And because real machines are not SSA, using separate variables (i.e., memory locations and registers) for everything is bound to be inefficient. The idea in SSA is to convert general programs into SSA form, do all our optimization there, and then convert back to a standard mutating form before we generate backend code.

Just renaming assignments willy-nilly will quickly run into problems. Consider this program:

If we start renaming all the occurrences of a , everything goes fine until we try to write that last print a . Which “version” of a should it use?

To match the expressiveness of unrestricted programs, SSA adds a new kind of instruction: a ϕ-node . ϕ-nodes are flow-sensitive copy instructions: they get a value from one of several variables, depending on which incoming CFG edge was most recently taken to get to them.

In Bril, a ϕ-node appears as a phi instruction:

The phi instruction chooses between any number of variables, and it picks between them based on labels. If the program most recently executed a basic block with the given label, then the phi instruction takes its value from the corresponding variable.

You can write the above program in SSA like this:

It can also be useful to see how ϕ-nodes crop up in loops.

(An aside: some recent SSA-form IRs, such as MLIR and Swift’s IR , use an alternative to ϕ-nodes called basic block arguments . Instead of making ϕ-nodes look like weird instructions, these IRs bake the need for ϕ-like conditional copies into the structure of the CFG. Basic blocks have named parameters, and whenever you jump to a block, you must provide arguments for those parameters. With ϕ-nodes, a basic block enumerates all the possible sources for a given variable, one for each in-edge in the CFG; with basic block arguments, the sources are distributed to the “other end” of the CFG edge. Basic block arguments are a nice alternative for “SSA-native” IRs because they avoid messy problems that arise when needing to treat ϕ-nodes differently from every other kind of instruction.)

Bril in SSA

Bril has an SSA extension . It adds support for a phi instruction. Beyond that, SSA form is just a restriction on the normal expressiveness of Bril—if you solemnly promise never to assign statically to the same variable twice, you are writing “SSA Bril.”

The reference interpreter has built-in support for phi , so you can execute your SSA-form Bril programs without fuss.

The SSA Philosophy

In addition to a language form, SSA is also a philosophy! It can fundamentally change the way you think about programs. In the SSA philosophy:

• definitions == variables
• instructions == values
• arguments == data flow graph edges

In LLVM, for example, instructions do not refer to argument variables by name—an argument is a pointer to defining instruction.

Converting to SSA

To convert to SSA, we want to insert ϕ-nodes whenever there are distinct paths containing distinct definitions of a variable. We don’t need ϕ-nodes in places that are dominated by a definition of the variable. So what’s a way to know when control reachable from a definition is not dominated by that definition? The dominance frontier!

We do it in two steps. First, insert ϕ-nodes:

Then, rename variables:

Converting from SSA

Eventually, we need to convert out of SSA form to generate efficient code for real machines that don’t have phi -nodes and do have finite space for variable storage.

The basic algorithm is pretty straightforward. If you have a ϕ-node:

Then there must be assignments to x and y (recursively) preceding this statement in the CFG. The paths from x to the phi -containing block and from y to the same block must “converge” at that block. So insert code into the phi -containing block’s immediate predecessors along each of those two paths: one that does v = id x and one that does v = id y . Then you can delete the phi instruction.

This basic approach can introduce some redundant copying. (Take a look at the code it generates after you implement it!) Non-SSA copy propagation optimization can work well as a post-processing step. For a more extensive take on how to translate out of SSA efficiently, see “Revisiting Out-of-SSA Translation for Correctness, Code Quality, and Efficiency” by Boissinot et al.

• One thing to watch out for: a tricky part of the translation from the pseudocode to the real world is dealing with variables that are undefined along some paths.
• Previous 6120 adventurers have found that it can be surprisingly difficult to get this right. Leave yourself plenty of time, and test thoroughly.
• You will want to make sure the output of your “to SSA” pass is actually in SSA form. There’s a really simple is_ssa.py script that can check that for you.
• You’ll also want to make sure that programs do the same thing when converted to SSA form and back again. Fortunately, brili supports the phi instruction, so you can interpret your SSA-form programs if you want to check the midpoint of that round trip.
• For bonus “points,” implement global value numbering for SSA-form Bril code.

IEEE Account

• Change Username/Password
• Update Address

Purchase Details

• Payment Options
• Order History
• View Purchased Documents

Profile Information

• Communications Preferences
• Profession and Education
• Technical Interests
• US & Canada: +1 800 678 4333
• Worldwide: +1 732 981 0060
• Contact & Support
• About IEEE Xplore
• Accessibility
• Terms of Use
• Nondiscrimination Policy
• Privacy & Opting Out of Cookies

A not-for-profit organization, IEEE is the world's largest technical professional organization dedicated to advancing technology for the benefit of humanity. © Copyright 2024 IEEE - All rights reserved. Use of this web site signifies your agreement to the terms and conditions.

🇺🇦    make metadata, not war

Static Single Assignment for Decompilation

• Michael Van Emmerik

Similar works

University of Queensland eSpace

This paper was published in University of Queensland eSpace .

Having an issue?

Is data on this page outdated, violates copyrights or anything else? Report the problem now and we will take corresponding actions after reviewing your request.

Native ×86 decompilation using semantics-preserving structural analysis and iterative control-flow structuring

New Citation Alert added!

This alert has been successfully added and will be sent to:

You will be notified whenever a record that you have chosen has been cited.

To manage your alert preferences, click on the button below.

New Citation Alert!

Please log in to your account

Information & Contributors

Bibliometrics & citations, view options.

• Botacin M Galante L de Geus P Grégio A (2019) RevEngE is a dish served cold Proceedings of the 3rd Reversing and Offensive-oriented Trends Symposium 10.1145/3375894.3375895 (1-12) Online publication date: 28-Nov-2019 https://dl.acm.org/doi/10.1145/3375894.3375895
• Becker M Pazaj M Chakraborty S (2019) WCET Analysis meets Virtual Prototyping Proceedings of the 22nd International Workshop on Software and Compilers for Embedded Systems 10.1145/3323439.3323978 (13-22) Online publication date: 27-May-2019 https://dl.acm.org/doi/10.1145/3323439.3323978
• Becker M Chakraborty S Metta R Venkatesh R Chen J Shrivastava A (2019) Imprecision in WCET estimates due to library calls and how to reduce it (WIP paper) Proceedings of the 20th ACM SIGPLAN/SIGBED International Conference on Languages, Compilers, and Tools for Embedded Systems 10.1145/3316482.3326353 (208-212) Online publication date: 23-Jun-2019 https://dl.acm.org/doi/10.1145/3316482.3326353
• Show More Cited By

Recommendations

Static analysis of jni programs via binary decompilation.

JNI programs are widely used thanks to the combined benefits of C and Java programs. However, because understanding the interaction behaviors between two different programming languages is challenging, JNI program development is difficult to get right and ...

Advanced static analysis for decompilation using scattered context grammars

Reverse program compilation (i.e. decompilation) is a process heavily exploited in reverse engineering. The task of decompilation is to transform a platform-specific executable into a high-level language representation, which is usually the C language. ...

Interprocedural Data Flow Decompilation

Information, published in.

• Program Chair:

University of Illinois and Adrenaline Mobility

• Akamai: Akamai
• Google Inc.
• IBMR: IBM Research
• Microsoft Reasearch: Microsoft Reasearch

USENIX Association

United States

Publication History

Contributors, other metrics, bibliometrics, article metrics.

• 27 Total Citations View Citations
• 0 Total Downloads
• Downloads (Last 12 months) 0
• Downloads (Last 6 weeks) 0
• Lacomis J Yin P Schwartz E Allamanis M Goues C Neubig G Vasilescu B Zimmermann T Lawall J Marinov D (2019) DIRE Proceedings of the 34th IEEE/ACM International Conference on Automated Software Engineering 10.1109/ASE.2019.00064 (628-639) Online publication date: 10-Nov-2019 https://dl.acm.org/doi/10.1109/ASE.2019.00064
• Katz O Rinetzky N Yahav E (2018) Statistical Reconstruction of Class Hierarchies in Binaries ACM SIGPLAN Notices 10.1145/3296957.3173202 53 :2 (363-376) Online publication date: 19-Mar-2018 https://dl.acm.org/doi/10.1145/3296957.3173202
• He J Ivanov P Tsankov P Raychev V Vechev M Lie D Mannan M Backes M Wang X (2018) Debin Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security 10.1145/3243734.3243866 (1667-1680) Online publication date: 15-Oct-2018 https://dl.acm.org/doi/10.1145/3243734.3243866
• Karande V Chandra S Lin Z Caballero J Khan L Hamlen K Kim J Ahn G Kim S Kim Y Lopez J Kim T (2018) BCD Proceedings of the 2018 on Asia Conference on Computer and Communications Security 10.1145/3196494.3196504 (393-398) Online publication date: 29-May-2018 https://dl.acm.org/doi/10.1145/3196494.3196504
• Jaffe A Lacomis J Schwartz E Le Goues C Vasilescu B Khomh F Roy C Siegmund J (2018) Meaningful variable names for decompiled code Proceedings of the 26th Conference on Program Comprehension 10.1145/3196321.3196330 (20-30) Online publication date: 28-May-2018 https://dl.acm.org/doi/10.1145/3196321.3196330
• Katz O Rinetzky N Yahav E Shen X Tuck J Bianchini R Sarkar V (2018) Statistical Reconstruction of Class Hierarchies in Binaries Proceedings of the Twenty-Third International Conference on Architectural Support for Programming Languages and Operating Systems 10.1145/3173162.3173202 (363-376) Online publication date: 19-Mar-2018 https://dl.acm.org/doi/10.1145/3173162.3173202
• Kim S Faerevaag M Jung M Jung S Oh D Lee J Cha S Rosu G Di Penta M Nguyen T (2017) Testing intermediate representations for binary analysis Proceedings of the 32nd IEEE/ACM International Conference on Automated Software Engineering 10.5555/3155562.3155609 (353-364) Online publication date: 30-Oct-2017 https://dl.acm.org/doi/10.5555/3155562.3155609

View options

Share this publication link.

Copying failed.

Share on social media

Affiliations, export citations.

• Please download or close your previous search result export first before starting a new bulk export. Preview is not available. By clicking download, a status dialog will open to start the export process. The process may take a few minutes but once it finishes a file will be downloadable from your browser. You may continue to browse the DL while the export process is in progress. Download
• Download citation
• Copy citation

We are preparing your search results for download ...

We will inform you here when the file is ready.

Your file of search results citations is now ready.

Your search export query has expired. Please try again.

• DOI: 10.14264/158682
• Corpus ID: 59779256

Static single assignment for decompilation

• Published 2007
• Computer Science

Figures and Tables from this paper

75 Citations

Recompile: a decompilation framework for static analysis of binaries, decompilation at runtime and the design of a decompiler for dynamic interpreted languages, cfg recovery control-flow structure recovery statement translation decompiler output binary tie and bap phoenix type recovery.

• Highly Influenced
• 11 Excerpts

Approaching Retargetable Static, Dynamic, and Hybrid Executable-Code Analysis

A human-centric approach for binary code decompilation.

• 10 Excerpts

No More Gotos: Decompilation Using Pattern-Independent Control-Flow Structuring and Semantic-Preserving Transformations

Comments recovery approach for java decompiler, preprocessing of binary executable files towards retargetable decompilation, decompiler for pseudo code generation, dewolf: improving decompilation by leveraging user surveys, 126 references, practical analysis of stripped binary code, analysis of virtual method invocation for binary translation, a taxonomy of obfuscating transformations, practical improvements to the construction and destruction of static single assignment form, recovery of jump table case statements from binary code, analyzing memory accesses in x86 executables, an incremental flow- and context-sensitive pointer aliasing analysis, llvm: a compilation framework for lifelong program analysis & transformation, reverse compilation techniques, computer security analysis through decompilation and high-level debugging, related papers.

Showing 1 through 3 of 0 Related Papers

Published in 2007

A Static Recognition Mechanism for Indirect Call Based on Static Single Assignment

• Conference paper
• Cite this conference paper

• Shixiang Gao 18 ,
• Tao Zheng 18 , 19 ,
• Xun Zhan 18 ,
• Xianping Tao 19 ,
• Qiaoming Zhu 20 ,
• Junyuan Xie 19 &
• Wenyang Bai 19  

Part of the book series: Lecture Notes in Computer Science ((LNCCN,volume 8351))

Included in the following conference series:

• Joint International Conference on Pervasive Computing and the Networked World

3057 Accesses

By preventing attacks which exploit stack buffer overflow vulnerabilities, address space layout randomization is an effective way for embedded systems protection. However, ASLR will probably suffer exhaustive attacks because the pertinence is not strong. At present only coarse-grained randomization has been implemented because one of the key bottlenecks for fine-grained randomization is the dependencies between functions cannot be constructed completely due to indirect calls. As a result, we give a static inter-procedural backtracking recognition mechanism in this paper by using intermediate code analysis technologies to identify the destination addresses of indirect callings generated by function pointers.

This work is funded by the National Natural Science Foundation of China under Grant No. 61373010 and the National High Technology Research and Development Program of China under Grant No. 2011AA01A202.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Subscribe and save.

• Get 10 units per month
• Download Article/Chapter or eBook
• 1 Unit = 1 Article or 1 Chapter
• Cancel anytime
• Available as PDF
• Read on any device
• Instant download
• Own it forever
• Compact, lightweight edition
• Dispatched in 3 to 5 business days
• Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Unable to display preview.  Download preview PDF.

Similar content being viewed by others

Untangle: Aiding Global Function Pointer Hijacking for Post-CET Binary Exploitation

FRProtector: Defeating Control Flow Hijacking Through Function-Level Randomization and Transfer Protection

SafeStack $$^+$$ : Enhanced Dual Stack to Combat Data-Flow Hijacking

Ravi, S., Raghunathan, A., Kocher, P., et al.: Security in embedded systems: Design challenges. ACM Transactions on Embedded Computing Systems (TECS) 3(3), 461–491 (2004)

Article   Google Scholar  

Hsieh, G., Meeks, R., Marvel, L.: Supporting Secure Embedded Access Control Policy with XACML+ XML Security. In: 2010 5th International Conference on Future Information Technology (FutureTech), pp. 1–6. IEEE (2010)

Google Scholar  

Cowan, C., Pu, C., Maier, D., et al.: StackGuard: Automatic adaptive detection and prevention of buffer-overflow attacks. In: Proceedings of the 7th USENIX Security Symposium, vol. 81, pp. 346–355 (1998)

Cowan, C., Barringer, M., Beattie, S., et al.: FormatGuard: Automatic protection from printf format string vulnerabilities. In: Proceedings of the 10th USENIX Security Symposium, vol. 3 (2001)

Solar Designer. StackPatch, http://www.opwnwall.com/linux

Bhatkar, S., DuVarney, D.C., Sekar, R.: Address obfuscation: An efficient approach to combat a broad range of memory error exploits. In: Proceedings of the 12th USENIX Security Symposium, vol. 120 (2003)

Kil, C., Jun, J., Bookholt, C., et al.: Address space layout permutation (aslp): Towards fine-grained randomization of commodity software. In: 22nd Annual on Computer Security Applications Conference, ACSAC 2006, pp. 339–348. IEEE (2006)

Shacham, H.: The geometry of innocent flesh on the bone: Return-into-libc without function calls (on the x86). In: Proceedings of the 14th ACM Conference on Computer and Communications Security, pp. 552–561. ACM (2007)

Jackson, T., Salamat, B., Wagner, G., et al.: On the effectiveness of multi-variant program execution for vulnerability detection and prevention. In: Proceedings of the 6th International Workshop on Security Measurements and Metrics, vol. 7. ACM (2010)

Shacham, H., Page, M., Pfaff, B., et al.: On the effectiveness of address space randomization. In: ACM conference on Computer and Communication s Security (CCS), Washington, DC, pp. 298–307 (2004)

Durden, T.: Bypassing pax aslr protection. Phrack Magazine 59(9), 9–9 (2002)

Wang, Z., Cheng, R., Gao, D.: Revisiting address space randomization. Information Security and Cryptology-ICISC 2011, 207–221 (2010)

Van Emmerik, M.J.: Static single assignment for decompilation. The University of Queensland (2007)

Appel, A.W.: Modern compiler implementation in Java. Cambridge University Press (1998)

Lang, B., Zhao, N., Ge, K., et al.: An XACML policy generating method based on policy view. In: Third International Conference on Pervasive Computing and Applications, ICPCA 2008, vol. 1, pp. 295–301. IEEE (2008)

Cytron, R., Ferrante, J., Rosen, B.K., et al.: Efficiently computing static single assignment form and the control dependence graph. ACM Transactions on Programming Languages and Systems (TOPLAS) 13(4), 451–490 (1991)

Cifuentes, C., Simon, D.: Procedure abstraction recovery from binary code. In: Proceedings of the Fourth European Software Maintenance and Reengineering, pp. 55–64. IEEE (2000)

Download references

Author information

Authors and affiliations.

Software Institute, Nanjing University, 210093, Nanjing, China

Shixiang Gao, Tao Zheng & Xun Zhan

National Key Laboratory for Novel Software Technology, Nanjing University, Nanjing, China

Tao Zheng, Xianping Tao, Junyuan Xie & Wenyang Bai

School of Computer Science & Technology, Soochow University, 215006, Suzhou, China

Qiaoming Zhu

You can also search for this author in PubMed   Google Scholar

Editor information

Editors and affiliations.

School of Logistics Engineering, Wuhan University of Technology, 430063, Wuhan, Hubei, China

Qiaohong Zu

Facultad de Ingenieria y Ciencias Universidad Adolfo Ibanez, Vina del Mar, Chile

Maria Vargas-Vera

Fujitsu, Hayes, Middlesex, UK

Rights and permissions

Reprints and permissions

Copyright information

© 2014 Springer International Publishing Switzerland

About this paper

Cite this paper.

Gao, S. et al. (2014). A Static Recognition Mechanism for Indirect Call Based on Static Single Assignment. In: Zu, Q., Vargas-Vera, M., Hu, B. (eds) Pervasive Computing and the Networked World. ICPCA/SWS 2013. Lecture Notes in Computer Science, vol 8351. Springer, Cham. https://doi.org/10.1007/978-3-319-09265-2_12

Download citation

DOI : https://doi.org/10.1007/978-3-319-09265-2_12

Publisher Name : Springer, Cham

Print ISBN : 978-3-319-09264-5

Online ISBN : 978-3-319-09265-2

eBook Packages : Computer Science Computer Science (R0)

Share this paper

Anyone you share the following link with will be able to read this content:

Sorry, a shareable link is not currently available for this article.

Provided by the Springer Nature SharedIt content-sharing initiative

• Publish with us

Policies and ethics

• Find a journal
• Track your research

Instantly share code, notes, and snippets.

chinmaydd / Chapter - 1.txt

• Download ZIP
• Star ( 0 ) 0 You must be signed in to star a gist
• Fork ( 0 ) 0 You must be signed in to fork a gist
• Embed Embed this gist in your website.
• Share Copy sharable link for this gist.
• Clone via HTTPS Clone using the web URL.
• Learn more about clone URLs
• Save chinmaydd/ce6fb6108ca97a316d1994dfe4da8a97 to your computer and use it in GitHub Desktop.