Jon Roelofs

Unconventional Calling

2020-02-02T00:00:00+00:00

JRoelofs Image

Recently a colleague and I were discussing some of the nuances of the ARM Procedure Call Standard, related to some work I did adding armv4t support to LLVM.

First, let’s take a step back and review what a “Calling Convention” is, and lay the ground rules for them on more modern ARM architectures before jumping into the weeds with armv4t. Calling conventions are a low-level contract describing how arguments may be passed to function calls, how return values are passed back, and set the division of responsibilities between caller and callee over saving and restoring registers before/after/during function calls.

ARM EABI has a particularly straightforward calling convention for C functions that denotes (ignoring VFP registers):

r0-r3 as caller-saved argument / scratch registers, with results passed in r0-r1
r4-r8 as callee-saved registers
r9 is either caller or callee saved, depending on the target platform
r10-r11 are callee-saved
r12-r15 are special-purpose registers (ip, fp, lr, pc)

Callee-saved registers must be saved by the called function, and caller-saved registers must be saved by the calling function. This particular allocation of a small number of caller-saved registers, with the bulk of the register set allocated as callee-saved registers favors small functions with fewer live ranges (and therefore less register pressure). This seems to be a good tradeoff since it allows small functions to avoid touching the stack to spill live ranges, and leaves a big set of registers for use in large functions where the cost of saving & restoring them is better amortized over the life of the function.

In practice, a C function like this:

int melanger(int lhs, int rhs) {
    return lhs + rhs
}

will most likely get lowered to something like:

melanger:
    add r0, r0, r1
    bx lr

Of note here is that the compiler passed lhs and rhs in r0 and r1 respectively, and the result was returned in r0. What’s also interesting is the bx instruction used for the jump back to the caller in that it allows “interworking” between the two instruction sets, Arm and Thumb, that most 32-bit ARM cores have on them. At branch time, depending on the parity of the pc stored in lr, the chip works out whether it needs to switch modes between Arm and Thumb to correctly decode the instruction stream. A fun side-effect of that is that all Thumb functions have odd addresses, and Arm functions have even addresses.

The call sites of this function will look something like this in the case of a direct call:

    mov r0, ...
    mov r1, ...
    blx melanger
    mov ..., r0

Indirect calls (ie. through a function pointer) look a bit different:

    mov r0, #1
    mov r1, #2
    ldr r3, .funptr
    ldr r3, [r3]
    blx r3
    mov ..., r0

And that brings me to one of the first weirditudes of armv4: there is no blx instruction, so indirect calls must use some other sequence. The most obvious candidate would be mov lr, pc; blx rN, but that has a subtle incompatiblity if you attempt to run such code on a newer ARM core, since the mov “magically” drops the parity bit, causing the instructions after the bx to be interpreted as Arm instructions… which whole rest of the toolchain isn’t prepared for.

Instead, we take advantage of the fact that the bl instruction saves off the link register, and create a sort of “branch island” to take care of the interworking bits:

    mov r0, #1
    mov r1, #2
    ldr r3, .funptr
    bl .island
    mov ..., r0

    ...

.island:
    bx r3

This avoids the broken sequence, and maximizes compatibility with a bunch of early ARM architecture variants. Iain Sandoe and I fixed that in r223380 if you’d like to take a look at the implementation details.

Another place that armv4 gets weird is during function prologues, which would normally leverage pop {..., pc} to restore various callee-saved registers, and jump back to the caller. Unfortunately on armv4, the pop instruction doesn’t restore the parity bit, so interworking through it is not permitted. Instead, we have to return through bx like so:

    pop {r3}
    add sp, #offset      # pop off whatever other stack we used
    bx r3

Things get even more complicated if the function needs to use r3 as part of the returned values, since now that hinders our ability to use that register to help with interworking. It is further complicated by the fact that there aren’t many other registers that we can even use for this. Any callee-saved register is obviously out of the question, since we need to use it after we’ve restored them. That limits us to a caller-saved one, or one of those special-purpose registers mentioned earlier. The best candidate is therefore the ip register, i.e. r12, which is reserved for the linker as a scratch register for use between function calls, and in that case we lower the prologue as:

    mov ip, r3           # shuffle part of return value into ip
    pop {r3}             # lr from the call site
    add sp, #offset      # pop off whatever other stack we used
    mov lr, r3           # shuffle return address into lr
    mov r3, ip           # restore r3 as part of return value
    bx lr                # return to caller

For those curious on the implementation details, I implemented this workaround in r214881.

Anatomy of a SOW

2019-12-15T00:00:00+00:00

Shutterstock Image

Writing good Statements of Work, or “SOW”s is one of the most important keys to success in any long term project. The structure it provides is often unseen until well into projects that have gone off the rails in one way or another. In this article, I’m going to walk through some of the things I’ve learned about writing them over the course of several projects for different clients.

In the early stages of a project, well before a SOW is even drafted, you’ll often go through a “design study” phase. During that period, the main ideas for the What, How, and Why of the project get fleshed out in broad terms, but with enough detail that someone familiar with the field could read it and get up to speed quickly on your project.

SOWs are similar to design studies and whitepapers, but more contractual, and slightly less technical. They are usually meant as a bridge between you and your client to lay out the terms of what you’re going to build. While you may get along well with them now, the document you’re writing should be a clear guide for the off-chance that something goes wrong with either their expectations, or yours. If you’re prepared for that, by having written a good SOW, it’ll be much easier to manage those expectations, and keep everyone on track.

Authoring

Like your project, it is important to have a good skeleton laid out in advance, as that guides you through writing it. SOWs have a pretty standard structure, and once you’ve written one, you have a template for all of the rest of them you’ll ever write.

Definitions

Defining your terms helps to make sure that everyone is on the same page. Often with technical work, there is quite a lot of jargon, with subjective waffly meanings. By writing down what you mean, things become objective and the intent is clarified. That way you, and your client can speak on even terms, with a reduced chance of misunderstanding.

Assumptions

Writing down your assumptions helps to limit the scope of whatever you didn’t expect. And surprises always show up when you least expect them (Ha! Imagine that!) so it’s best to prepare for them as much as you can. By preparing for the unexpected, you’ll be giving yourself more room to negotiate later.

Abstract

Like any academic paper, it is useful to have a quick preliminary summary of what the project is about, and why it’s going to get built. This explains to the non-technical managers, sales-people, and finance-critters the Big Picture ™ of what you’re trying to accomplish. You’ll want this section to be short and concise in order to keep from losing their attention, but general enough to give them a working understanding of the project. Think of what you’d say in an Elevator Pitch, and put that in this section. Use keywords from your Definitions section, but don’t get too technical.

Purpose

This section is a good place to put the summary of the technical details. If the Abstract was the view from the plane at 10km staring down at the top of Everest, you’ll want this section to be right there at 8848m giving concrete details.

Deliverables

Deliverables are the bacon of a SOW, the raison d’être of a project. Often they are intermediate steps along the way to completion of a project, representing some modest amount of progress. Sometimes they are a finished product, other times they are a snapshot of development, or even a significant event like publishing a website or achieving successful bringup on a new piece of hardware.

Each deliverable should be something self-contained, with a clear purpose. If you can put a simple name on it, even better, because you’re going to be referring to it a lot.

Milestones

Milestones lay out the schedule of what is going to be built when, and by whom.

For a fixed-fee structured contract, it is a really good idea to structure the delivery dates of each milestone such that they’re relative to the other milestones they depend on. For example, if a farmer has two milestones, M0 and M1, say, for raising a litter of piglets and delivering them to the butcher once they’ve matured, then his M1 depends on M0. Since he’s done this many times before, he knows it takes about 4 months to raise a piglet to maturity. Instead of writing down in his SOW that he expects his Sow to give birth in January, with delivery to the butcher in May, he should give an estimated time for M0, and a relative time of M0 + 4mo for M1s delivery date. This protects him from something he doesn’t have a lot of control over: when the Sow delivers.

In a services organization, it isn’t advisable to promise too much about who specifically is going to be doing what work. Engineers are mostly interchangable, and frankly, your client shouldn’t care. On the other hand, it is good to clear up which parts of the project you will be implementing, and which parts of it your client needs to do. The Milestones table is a good place for that.

Acceptance

Acceptance criteria are the rubrics by which you measure completion of a project. It is critical that they be well defined, and objective so that you and your client can agree when Done is Done.

Sometimes projects call for the Acceptance Tests to be determined later in the project, instead of them being decided up front. That usually comes up when the experience of building each of the deliverables is thought to give more clarity on how to actually define “Done”. Be careful writing such an agreement however, since it lets some subjectivity and wiggle room in through the back door. While it may allow you more flexibility later, it comes with the price of allowing your customer to force scope-creep. Usually the latter overshadows any benefit of the former unless you’ve already developed a good working relationship with them.

Budget

The budget section of a SOW describes the payment schedule over the course of the project. Usually payments are contingent upon achieving milestones, and tied to making successful deliveries. Occasionally you might find a project where a “Pay for Performance” style of incentive is warranted. In those cases, it’s a good idea to negotiate up front what the limits are, so that neither party to the contract is surprised by having to pay too much / recieve too little respectively.

Agreement

Finally, the Agreement section is where the SOW becomes a contract, since this is where the signatures go. It’s important to get everyone on board with the all of the details before signing, so don’t sign your portion of it before you’ve achieved consensus with your client. A good way to protect yourself during this period, is to lock the document & track the changes. While Git is a good tool for that as far as developers are concerned, the finance and legal-critters tend to get scared off by it; better just use the tools in Microsoft Word to do that, it’ll make them happier. After all, a happy salesperson is a good ally to have: they will go to bat for you when you need them.

Appendix

Appended to the end of your SOW should be any supplemental materials that don’t fit well in the structure above. Refer to these in your descriptions where they provide useful insight that would otherwise take several pages to explain.

About

2017-11-24T00:00:00+00:00

For organizations that need to develop secure, cryptocurrency solutions in a rapidly developing marketplace, my unique approach to embedded systems engineering coupled with my expertise in compiler development ensures that your products and services will be secure, efficient, and innovative. Furthermore; my experience in open source development processes will enable development of collaborative relationships within the complex cryptocurrency markets ensuring a role of leadership, innovation, and trust.

What Next

For the past seven years I have been a team player on a variety of cutting edge technology projects for Intel, AMD, and Siemens. I am ready for an engineering-focused leadership role on my next technology development project. I am excited about cryptocurrencies, and have a strong background in compilers; combining the two wold be amazing.

What’s Important

Being able to grow and lead a high performing team.
Creating innovative technological designs and elegant solutions.
Working closely with technology enthusiasts and early adopters.
Supporting business development with my technical expertise.
Building efficient, honest and collaborative teamwork.

Competency Categories

Systems Design
- Define customer requirements
- Translate business requirements into development specs
- Scope, draft, and negotiate statements of work
- Concise and clear verbal & written communication skills
Software/Firmware Architecture
- Architect optimizing compilers for modern embedded processors
- Expert in SoC/GPU/FPGA acceleration of image processing algorithms
- Strong understanding of hardware development lifecycles
- Deep knowledge of blockchain technologies and their respective markets
Progamming
- Expert-level C/C++/ObjC programming skills and standards knowledge
- Experienced in cross-platform development
- Excellent embedded debug and problem solving skills
- Well versed in compiler tooling for static and dynamic analysis
- Proficient in Python, Bash, Javascript, and HTML
Leadership & Innovation
- See the big picture
- Help people create innovative solutions
- Respected member of the open source community
- Proven track record of informative, patient, and accurate support
Project Management
- Passion for building high quality software on time & on budget
- Tracks priorities, motivates others
- Self-starting, self-motivated, self-directed, and self-sufficient

Private Keys, Dragons, and C++: Part 1

2017-11-22T00:00:00+00:00

LLVM Wyvern, used with permission from llvm.org

Managing the lifetime of private keys in C++ is a difficult task. From memory management to compiler optimizations and undefined behavior, everywhere you turn, there are dragons waiting to break the security of even the most well-written standards-conforming code, and steal the keys to your castle. In this series, I describe common pitfalls when securing data while resident in memory and the industry-standard strategies for mitigating them.

In the first article of this series, we’ll examine an example from Monero. In Monero, one of the ways private keys are represented is with the following class hierarchy:

namespace crypto {
  struct ec_scalar {
    char data[32];
  };

  struct secret_key : ec_scalar {};

  struct public_key : ec_scalar {};
}

These POD or “Plain Old Data” structs are used all over the codebase as stack variables. A good representative example is where Monero’s wallet derives the private key from the user’s Electrum recovery sentence:

bool WalletImpl::recover(const std::string &path, const std::string &seed)
{
    clearStatus();
    m_errorString.clear();
    if (seed.empty()) {
        m_errorString = "Electrum seed is empty";
        LOG_ERROR(m_errorString);
        m_status = Status_Error;
        return false;
    }

    m_recoveringFromSeed = true;
    crypto::secret_key recovery_key;
    std::string old_language;
    if (!crypto::ElectrumWords::words_to_bytes(seed, recovery_key, old_language)) {
        m_errorString = "Electrum-style word list failed verification";
        m_status = Status_Error;
        return false;
    }

    try {
        m_wallet->set_seed_language(old_language);
        m_wallet->generate(path, "", recovery_key, true, false);

    } catch (const std::exception &e) {
        m_status = Status_Critical;
        m_errorString = e.what();
    }
    return m_status == Status_Ok;
}

Here the code does some error checking, converts the recovery sentence to binary form stored in our crypto::secret_key, and attempts to generate the wallet from that. If generation fails and an exception is thrown, it is handled and the error is logged.

From a key security standpoint, there are a few different areas where this code leaks the data of the private keys, in a way that other vulnerabilities might be able to take advantage of it. Mind you, I’m only describing best practices here, not an actual exploited vulnerability, so don’t get all doom and gloom on me.

The main leakages come from stale data on the stack. This happens as a result of C++’s mantra that one only pays in performance for the features they use. In this case, that relates to the fact that most C++ programs are not so hypersensitive to security issues, as those that handle financial transactions, like cryptocurrency wallets. Optimizing compilers, on the other hand, are very sensitive to performance concerns, with their goal being to make standards-comforming code as fast as possible. The difference in goals here means that the programmer has to take special care to manage the lifetime of their data.

The upside however, is that these are solvable problems. Let’s talk about the stack. Distilling the above example down, we have this roughly equivalent snippet:

bool words_to_bytes(const std::string &seed,
                    crypto::secret_key *key);

bool generate(crypto::secret_key *key);

bool recover(const std::string &seed) {
  crypto::secret_key recovery_key;

  if (words_to_bytes(seed, &recovery_key))
    return FAIL;

  if (generate(&recovery_key))
    return FAIL;

  return SUCCESS;
}

Consider what the stack might look like just after the words_to_bytes() call:

      +------------------------------+
sp -> |   return val  = false        |           words_to_bytes's frame
      +------------------------------+
      |   recovery_key               |           recover's frame
      |     data[0]  = 's'           |
      |     data[1]  = 'e'           |
      |     data[2]  = 'k'           |
      |     data[3]  = 'r'           |
      |     data[4]  = 'i'           |
      |     data[5]  = 't'           |
      |     data[6]  = ' '           |
      |     data[7]  = 'i'           |
      |     data[8]  = 's'           |
      |     ...                      |
      |     data[30] = '4'           |
      |     data[31] = '2'           |      heap
fp -> |   return addr = &caller + 24 |       ^
      |   seed = -------------------------\  |
      +------------------------------+    |  |
      |   seed                       |<---/  |   caller's frame
      |     ptr = ---------------------------/
      |     len = 37                 |
      |   return addr = ...          |
      |   ...                        |

If generate() fails, and we return to recover()s caller, the secret data in recovery_key will be left as garbage on the stack. This is undesriable because it leaves the data exposed to exploits that inspect the stack. Ideally, the sensitive data in the keys should be resident in memory for precisely as long as it is needed, and no longer.

A similar issue arises in the original example in the thrown path. There, the unwinder walks down the stack, perforing any cleanups along the way (i.e. destructors), leaving everything else untouched for performance reasons. Since, as platform maintainers, we want our user’s programs to be quick and responsive, this is usually a good tradeoff.

Luckily, we’re writing c++, and we can write a destructor that scrubs the key’s memory on scope exit, or during one of those unwinder cleanups. Doing so in C is still possible, but takes a bit more manual management of the data. Our first attempt might look something like:

namespace crypto {
  struct ec_scalar {
    char data[32];
  };

  struct secret_key : ec_scalar {
    ~secret_key() {
      memset(data, sizeof(data));
    }
  };
}

Unfortunately, the compiler decides to be “helpful” and optimize out the memset. Careful readers will have noticed that I had to defeat the optimizer once already, in order to keep it from optimizing doit() all the way to a nop. The trick there was to call through a volatile function pointer. Since volatile acts as a sort of optimization barrier as far as the compiler is concerned, it keeps the dead code elimination pass from touching our call. In other words, volatile scares off dragons. If we use the same trick again, it forces the compiler to keep the memset call.

This pattern is needed often enough that the standards body for C11 added it under the name memset_s. On BSD platforms, there is explicit_bzero, and likewise Windows has SecureZeroMemory. They’re all written with slightly different tricks, but all with the purpose of forcing the optimizer to leave seemingly dead code alone.

As with all such dragons’ dens, tread carefully and ask the advice of your local compiler expert before writing such code. It’s really tricky to get right, and there are many traps you can fall into. In the second article in this series, I’ll tell you all about page tables and memory being written to disk behind your back.

Stay tuned ‘till next time.