Looking at this code, what would you anticipate the respective values of variables ’n’ and ‘k’ to be?
Despite the confidence expressed in the blogosphere and forums, a number of software engineers would be incorrect….
To understand why ‘k’ increments in this way, we need an abbreviated understanding of how the function’s operations are managed.
For these examples, we are using a 64 bit machine, Ubuntu 14.04 LTS, GCC 4.8.4, and 3.13.0–107-generic GNU/Linux.
As we’ve covered in prior posts, when you compile a program (obviously, comprised of arguments and variables), it goes through a multitude of steps to be executable. The executable arguments and variables need a place to be stored, so that it can be managed and manipulated — resulting in the fulfillment of the function’s requests and directives. This is where the loader comes into play; the loader creates a space of virtual memory addresses where our stack — as well as many other things — will be located. The stack is a data structure that has “last in first out” (LIFO) data storage; the first information entering the stack has a higher memory address, whereas the addition of subsequent information “grows” downward — having a lower memory address.
The stack’s data is navigated and controlled by registers. Registers allow for fast processing and internal memory storage without having to access the physical memory. There are eight 16 bit general registers — ax, bp, bx, cx, di, dx, si, and sp (they are case insensitive) — that handle respective tasks. Depending on the operation, program, or processor different register size is required. Extended 32 bit versions can be accessed with the prefix “e”, and the long 64 bit size by prefixing with an “r”.
These are the basics (starting with the two most fundamental); having a reference for their utility will help you understand some object code…
BP, EBP, RBP is the base pointer which points to the address of the bottom of the stack; it’s a fixed reference point for the corresponding function’s parameters and variables within that stack frame.SP, ESP, RSP on the other hand, is the stack pointer to the address of the top of the stack.AX, EAX, RAX alongside DX, is responsible for arithmetic operations. It aids with transferring data.BX, EBX, RBX is a data pointer — only register capable of indirect addressing.CX, ECX, RCX does loop counting.DI, EDI, RDI is the pointer to destination in string and memory operations.DX, EDX, RDX handles input/output as well as arithmetic operations.SI, ESI, RSI is the pointer to source in string and memory operations.Moving forward (with all that in mind), what exactly is happening when we initialize k as k++? What exactly is happening in the machine code (or assembly code) that results in this output? Finding the answer to this question inches us closer to the exciting realm of reverse engineering.
In order to fully investigate this, there is a program called objdump we can use within the Linux shell that allows us to “see” inside the machine code. Before jumping into my explanation, let’s review this program:
objdump is a program for displaying various information about object files. As you will recall from our previous posts, object code is generated during the third stage of compilation, also called assembly. In order to help us parse through the information displayed using objdump we will run it with several options:
-j Display information only for a specified section — today we will only be reviewing two sections:.rodata — this is where read-only data is stored.text this is the program’s actual code (the assembly) — _start and main are both part of this section-s Displays the full contents of any sections requested. By default all non-empty sections are displayed.-M Assembly has two versions of syntax — AT&T or Intel. We use -M intel to tell objdump to display output in intel format.-d Display the assembler mnemonics for the machine instructions from objfile. This option only disassembles those sections which are expected to contain instructions.-S Display source code intermixed with disassembly, if possible. This is helpful because it will show the lines from our program.Now that we’ve reviewed objdump — let’s combine that with our investigation into what happens when we specify that k=k++.
The above tells us where the read-only data is stored.
objdump with the above option flags produces our object code with our source code intermixed in the output. In fact, many lines of object code are produced and we are only referencing the section with our source code. To view all of the object code, click here.
There are definitely lots of cool things happening there. Before we proceed, let’s review machine instructions. According to this guide, “machine instructions generally fall into three categories: data movement, arithmetic/logic, and control-flow.” In the above screenshot, the data movement instructions occur in the second to last column.
A short summary of data movement instructions:
mov — Move — this instruction copies data item referred to by its second operand into the location referred to by its first operand. For example:mov eax, ebx — copy the value in ebx into eaxpush — push stack — this instruction places its operand onto the top of the hardware supported stack in memory. For example: push eax — push eax on the stackpop — pop stack — this instruction removes the 4-byte data element from the top of the hardware-support stack into the specified operand. For example: pop edi — pop the top element of the stack into EDIlea — Load effective address — the instruction places the address specified by its second operand into the register specified by its first operand. Keep in mind, the contents of the memory location are not loaded, but only the effective address is computed and placed into the register. For example: lea eax, [var] — the value [var] is placed in EAXThere are arithmetic, logic and control flow instructions that I will not delve into more — for the purposes of this post, you will need to only know the above as well as one more:
call subroutine call — this control flow instruction pushes the current code location onto the hardware support stack in memory and then performs an unconditional jump to the code location indicated by the label operand. This instruction saves the location to return to when the subroutine completes.Size directives
BYTE PTR indicates size of 1 byteWORD PTR indicates size of 2 bytesDWORD PTR indicates size of 4 bytesNow that we know what machine instructions are, let’s step in and see what’s happening at a granular level in our program.
The instructions here tell the machine to copy the 32-bit integer representation of 0x62 into the stack at the address rbp-0x8. Remember, since we are compiling our program on a 64-bits machine running Ubuntu 14.04 LTS our integers will be 4 bytes long.
In case you were wondering what in the world 0x62 has to do with k = 98, a simple Google search reveals that 0x62 is the hexadecimal representation of the number 98.
So, at this moment, k = 98 — we know this because the machine instructions above corresponds to the C code k = 98 and the equivalent of k is stored at address rbp-0x8 in our assembly code.
Now, when we initialize our variable n to equal k++ we see the following happen in this order:
rbp-8 (the equivalent of k in our C code) — 98 — and copied to the register eaxeax is a subregister of rax. Since eax contains 98, this line of machine instruction indicates that we are adding 98+1 and storing the result into edxedx (99) is copied to the location referred to by rbp-0x8. Since rbp-0x8 is the equivalent of k , now k = 99.eax (98) is copied to the location referenced by rbp-0x4. This means by the end of this line of instruction, n = 98.As you can see, by the end of the fourth machine instruction, the original value of 98 is called. Similarly, we see the same as above instructions happen in the next two lines of code.
The only part where this is different from the above code is that the value of eax(98) is copied to the location referenced by rbp-0x8.
At this point, we know that both rbp-0x8 and rbp-0x4 carry the value of 98. From here the values are stored and then the call instruction tells program to use printf function to print the stored values to standard output.
Lastly, we see that the value of 0x0 is copied into eax — eax will store the return value of the functions. The return value of main will be 0, meaning that the program successfully ran.
So, from this, we can conclude that k = k++ returns k. Why? Well, k++ does in fact increment 98 to 99. The stored value resets the value of k to 98 by the end of the program. In other words, the iteration is only performed on a value stored in temporary location and that location was not called by the program.
Elaine Yeung is an elementary school dean turned software engineering student at Holberton School.
Naomi Sorrell is an enthusiastic tech newbie at Holberton School that enjoys man pages, fitness, and traveling
“Assembly Language Tutorial.” Assembly Language Tutorial. N.p., n.d. Web. 11 Mar. 2017.
Bacon, Jason W. “10.7. The Stack Frame.” 10.7. The Stack Frame. N.p., Mar. 2011. Web. 23 Mar. 2017.
Dang, Bruce, Alexandre Gazet, Elias Bachaalany, and SeÌbastien Josse. Practical Reverse Engineering: X86, X64, ARM, Windows Kernel, Reversing Tools, and Obfuscation. Indianapolis, IN: Wiley, 2014. Print.
Koopman, Phillip. “Stack Computers: 9.2 VIRTUAL MEMORY AND MEMORY PROTECTION.” Stack Computers: 9.2 VIRTUAL MEMORY AND MEMORY PROTECTION. N.p., 1989. Web. 11 Mar. 2017.
“Memory Layout of C Programs.” GeeksforGeeks. N.p., 30 Nov. 2016. Web. 11 Mar. 2017.
Milea, Andrea. “Dynamic Memory Allocation and Virtual Memory.” Understanding Virtual Memory and the Free Store (heap) — Cprogramming.com. C Programming, n.d. Web. 11 Mar. 2017.
“Stack (abstract Data Type).” Wikipedia. Wikimedia Foundation, 11 Mar. 2017. Web. 11 Mar. 2017.
Tutorialspoint.com. “Operating System — Virtual Memory.” www.tutorialspoint.com. N.p., n.d. Web. 11 Mar. 2017.
Tutorialspoint.com. “Assembly Registers.” www.tutorialspoint.com. N.p., n.d. Web. 11 Mar. 2017.
“Virtual Memory.” Wikipedia. Wikimedia Foundation, 10 Mar. 2017. Web. 11 Mar. 2017.
“X86 Assembly Guide.” Guide to X86 Assembly. University of Virginia Computer Science, 1 Jan. 2017. Web. 11 Mar. 2017. http://www.cs.virginia.edu/~evans/cs216/guides/x86.html
Pinterest — “the world’s catalog of ideas” — is built on open source, according to Jon Parise, technical architecture lead and open source program lead at the company. In this interview, Parise explains how adopting open source has changed the company and helped the company’s engineers design software that is more modular, reusable, and well-documented from the outset.
Pinterest also frequently open sources technology they build “as both a way to give back to communities and because it’s the right thing to do,” Parise says. Read on to learn more about how Pinterest uses and contributes to open source.
Linux.com: What does Pinterest do?
Jon Parise: Pinterest is the world’s catalog of ideas, used by 150 million people every month to discover and do things they love.
Linux.com: How and why do you use Linux and open source?
Parise: Pinterest is built on open source. From our first lines of Django code over six years ago to the release of Rocksplicator, our latest open source project, we’ve directly benefited from open source projects and the supportive communities surrounding them. In turn, we’ve made significant contributions to the open source technologies we use and have pushed the limits of technologies like HBase. Internally, open source is part of a product cycle. We frequently open source the technologies we build as both a way to give back to communities and because it’s the right thing to do.
Linux.com: Why did you join The Linux Foundation?
Parise: The Linux Foundation is home to Linux, Node.js and other mission critical projects that form the backbone of modern internet services, including Pinterest. Joining the Linux Foundation is great way for established companies like ours to support those communities.
Linux.com: What interesting or innovative trends in your industry are you witnessing and what role do Linux and open source play in them?
Parise: We’re excited about three big technology trends: machine learning, computer vision and rich media.
Almost all machine learning efforts at Pinterest rely on open source components to some extent. Our data processing pipelines run on Hadoop, Cascading and Scalding. We use TensorFlow, Caffe and XGBoost to train our models, and R and Python are widely used for analyzing the results produced.
Our Visual Search team uses open source libraries for deep learning and computer vision. Caffe, TensorFlow and OpenCV are critical building blocks at Pinterest and allow us to actively publish our algorithmic and implementation findings for building performant visual search systems.
Lastly, our video and image platform leverages libraries like FFmpeg, GraphicsMagick, and ExoPlayer to power efficient media processing and playback.
Linux.com: How has participating in open source communities changed your company?
Parise: As we’ve grown and are better resourced, we can now be a better contributor to open source by designing our software to be modular, reusable and well-documented from the beginning. In addition to making it easier for us to open source parts of our software down the road, that mindset benefits us in our day-to-day work as engineers inside the company, too.
We also strive to be additive to the greater open source community by filing bug reports, contributing patches, publishing papers, hosting tech talks and meetups, and speaking at conferences. Those are important things everyone can do, both as individuals and as employees of companies that benefit from open source.
Linux.com: How do you participate in the TODO Group and what have you learned from the experience?
Parise: It’s early for us as members, but we’re excited to participate in a group of like-minded companies committed to open source. In particular, TODO focuses on how companies can run effective open source programs both internally and externally. Pinterest has already released over 30 open source projects, and with untold more to come, the benefit of TODO’s collective experience has already proven invaluable.
Learn more about Linux Foundation corporate membership and see a full list of members at https://www.linuxfoundation.org/members/join.
Years after Intel released the low-power, Linux-compatible Quark X1000 processor, which runs on the Intel Galileo and numerous IoT gateways, the chipmaker last year launched three microcontroller-like Quarks that do not run Linux. Like the original Quarks, the Quark D1000 is limited to Pentium ISA compatibility and supports only bare metal implementations. The Quark D2000 and similar Quark SE C1000, which drives the Intel Curie module, also supply full Intel x86 ISA. They lack an x86 FPU but can still run RTOSes like Zephyr.
Considering the minimal MCU footprint, and lack of Linux-associated technologies like U-Boot, Intel had to develop a Quark D2000/SE bootloader from scratch. At the Embedded Linux Conference in February, Intel software engineer Daniele Alessandrelli detailed the inner workings of the Intel Quark Microcontroller Bootloader (QM-Bootloader). In his presentation, Alessandrelli also described security extensions added to version 1.4 of the BSD-licensed QM-Bootloader.
Designed for the D2000 and SE C1000, the QM-Bootloader offers typical bootstrap features such as system initialization, trim code computation, and restore context from sleep. It also provides Firmware Management (FM) functionality based on the DFU (Device Firmware Update) protocol and its most popular host tool, dfu-util.
Alessandrelli and his team needed to adapt dfu-util to work over UART as well as USB. This would provide a uniform firmware-upgrade experience whether developers were working with the USB 1.1-enabled SE or the standard D2000, which lacks USB support.
The D2000 and SE Quarks both feature 32MHz, x86-based Lakemont cores, but only the SE offers a 32MHz ARC sensor subsystem core. Further complicating the QM-Bootloader development process was the fact that the SE provides more memory: 80kB SRAM and 384kB flash. Both models, however, conveniently share an 8kB allotment of OTP (one-time programmable) SRAM.
“From the bootloader point of view the two Quarks are quite similar because we put our bootloader in OTP,” said Alessandrelli, who, together with Jesus Sanchez-Palencia, is the
maintainer of the project. “The 8kB limitation was a restraint, but we were still able to implement a modular approach so we could add new transports and potentially OTA updates in future.”
The foundation of the QM-Bootloader is the DFU protocol, which provides a way to transfer data to the device with DFU_DNLOAD for FM, as well as extract data with DFU_UPLOAD. Both are block-based mechanisms: All blocks except the last must have the same size.
“We decided to use DFU because it is open source, well documented, and designed for resource constrained devices,” said Alessandrelli. “Also, DFU doesn’t define any specific image format, and we wanted to do our own image format with its own metadata and authentication mechanism. We don’t have enough RAM or flash to store a full image, so we needed to develop our own block-wise transfer/flashing protocol to allow us to write an image a block at a time.”
To adapt DFU for UART, the Intel team created a Quark DFU Adaptation (QDA) protocol. “QDA makes DFU available over any message transport,” said Alessandrelli. “Because UART is stream oriented, we added the old XMODEM-CRC protocol layer to transport QDA packets. QDA provides all DFU request/response messages, such as DFU_UPLOAD, and also mimics some generic USB functionality, including active alternate settings. We needed a different host code for QDA/UART, so we modified dfu-util to replace the USB layer with QDA/UART.” The resulting qm-dfu-util code is available on GitHub, licensed under GPLv2.
On top of the QDA layer, the Intel team defined a Quark Format Upgrade (QFU) image format that works with generic DFU tools and supports firmware authentication. This “very simple block-wise format” adds a header to the first block of the binary, “so it’s processed before the image,” said Alessandrelli. The header is subdivided into a base header, which contains information like the target device and the vendor and product ID, as well as an extended header used for authentication.
“We do not add any specific memory address to the header, but instead assume the flash is divided into partitions, and that every image is targeting a partition,” said Alessandrelli. This setup enables the bootloader to support a single partition on the D2000, and two partitions on the ARC-enabled SE model. This also enables future schemes such as multiple partitions per core, which might come in handy for OTA.
Finally, the Quark Firmware Management (QFM) protocol runs on top of the DFU layers, thereby enabling functionality beyond firmware upgrade, such as key provisioning, application erase, and system/firmware information retrieval. QFM is basically a request (DFU_DNLOAD ) or response (upload) protocol.
Alessandrelli went on to describe new Secure Firmware Upgrade extensions that have been added to QM-Bootloader 1.4’s QFM layer to enable authenticated firmware upgrades. Due to the Quark’s limitations, he could not use a public key scheme. Instead, he chose a simple symmetric key scheme called HMAC256.
“With HMAC, the image is verified using the same key that is used to sign it, and the key must be located within the device,” said Alessandrelli. “We decided not to hard-code the key, but instead provided users with the key management functionality so at runtime they can provide the key.”
The QFU header is extended with an HMAC extended header. “We don’t compute the HMAC for the entire image, but we authenticate the header, adding an array of hashes, one for each block that composes the image,” said Alessandrelli. “We authenticate the header using HMAC, then start receiving blocks of images.We compute the SHA of every block and compare it with the SHA in the header.”
The security enhancements address the challenge of ensuring partition consistency — how to handle failures that can leave partitions in an inconsistent state, for example, due to a reset during a firmware update. The new code associates a consistency flag to every partition and stores this metadata in a bootloader file called BL-Data.
The updated bootloader also adds key management. “We basically define and authenticate a key update request, an extension of QFM,” said Alessandrelli. “We use double-signing, providing both the firmware key, which is used to authenticate an image, as well as a revocation key.” Although this scheme will need to be modified if they add OTA support in the future, “since right now we’re only supporting wired and point to point USB or UART transfer, a man in the middle attack is defeatable,” he noted.
Alessandrelli also described security enhancements used to protect BL-DATA using CRC and further explained how partitions are related to targets. The enhancements are designed to support future upgrades to OTA and other additions, such as BLE modules with their own firmware.
Alessandrelli concluded with some lessons learned, such as the importance of reusing existing open source code and using a modular approach. “By not pre-optimizing for footprint, we can adapt to changing requirements,” he said. “By using link-time optimization, we could offset most of the overhead from the modular approach, giving us 15 to 20 percent savings in flash footprint saving.”
Watch the complete presentation below.
Connect with the Linux community at Open Source Summit North America on September 11-13. Linux.com readers can register now with the discount code, LINUXRD5, for 5% off the all-access attendee registration price. Register now to save over $300!