Rant of the Week (ROTW): Trusted vs. Trustworthy

A common theme in computer security is "trust" -- and the implication that trust is equal to security is prevalent in quite a bit of literature and propaganda.  Although Wikipedia isn't the greatest source, it does provide some insight into popular beliefs, and makes for a good vehicle for this discussion.  Consider the article on the Trusted Platform Module, which starts with:

In computing, Trusted Platform Module (TPM) is both the name of a published specification detailing a secure cryptoprocessor that can store cryptographic keys that protect information, as well as the general name of implementations of that specification, often called the "TPM chip" or "TPM Security Device"

So what? Follow the links, and we get a little closer to some understanding:

A secure cryptoprocessor is a dedicated computer on a chip or microprocessor for carrying out cryptographic operations, embedded in a packaging with multiple physical security measures, which give it a degree of tamper resistance.

And there is the key: tamper resistance. Security is a much-bandied word in the computing field, but the notion that just because something is trusted it is secure is ridiculous. But there is also a subtle distinction between tamper resistance and tamper proof. My view is that you need to be tamper proof to be secure in the physical attack model, and tamper resistance just gets you security against amateur hackers.  Unfortunately, it is prohibitively expensive to manufacture tamper proof electronics, and even worse is that tamper proofing the system only gives you physical security--you still need a trustworthy system underneath the tamper proof layer.  That said, the TPM provides a very good approach to building security, but it is not perfect.

Assuming the TPM is trustworthy, one useful application of the TPM is to get a trusted boot, which provides a good basis for building secure systems.  However, without tamper proofing the TPM, there is no guarantee that a sophisticated attacker won't be able to circumvent the security mechanisms.  An example of this is the Reset attack, demonstrated against an early version of the TPM specification.  These types of attacks show that even if the module is "trusted", it can still be manipulated to violate the security benefits of its use.  This applies even if the module is trustworthy, because these attacks manipulate the system interface to the module itself, which could also be a threat with a tamper proof system.

Some technical but approachable blog articles have been written over at the Invisible Things lab that address trusted technology and trusted boot, with an eye to the practical:

• ITL: Attacking Intel TXT
• ITL: Microsoft Bitlocker and Trusted Boot

The moral of the story is that trusted does not imply trustworthy, and that security is more complicated than trust alone.

Read More

Scripting with Lua

For about two weeks, I've been planning to put together a way to generate test cases for one of my current projects. The project involves adding new capabilities to the RTEMS scheduler, and to test it I need to create RTEMS applications that spawn various periodic and aperiodic tasks. I already had written two such applications by hand, but I found it tedious to generate the parameters.

At a high level, the parameters are task type (periodic or aperiodic), duration (execution time), period, relative deadline, and release time (a.k.a. phase). To spawn tasks, I had some arrays defined in my RTEMS code of length equal to the number of total tasks. These arrays hold the values of the period, priority (relative deadline), release time, and execution time. Then my code uses the arrays to generate tasks with the given parameters. This isn't too difficult to write up by hand, but my project also requires that I compute some runtime characteristics of the periodic tasks.



In particular, I am implementing a static slack stealer in RTEMS, which requires a pre-computed table of all the jobs released in a hyperperiod. A job is an instance of a periodic task, which is released at a specific time and has an absolute deadline by which it must complete. The absolute deadline of a job is equal to the release time plus the task's relative deadline. A hyperperiod is a length of time equal to the least common multiple of all the periods of periodic tasks, which is the time it takes for the system to "cycle" the periodic tasks. At the start of a hyperperiod, the periodic tasks execute identically the same as at time 0 (or the start of the first hyperperiod).

The pre-computed table involves computing for each job in a hyperperiod the slack of the job, which is the difference between the job's deadline and the sum of all the execution times of jobs with earlier deadlines. Then each w(i,j) entry of the pre-computed slack table w is the minimum of jobs with deadlines greater than or equal to i and less than or equal to j. The slack table is an N x N upper-triangular matrix, where N is the number of jobs in a hyperperiod. Calculating these values by hand is tedious, so I decided to implement a script to automatically generate the pre-computed slack table for a given set of periodic tasks.

I don't do very much scripting work, so I have no preference on language. Most of the time I can get away with shell scripts. But in this case, I wanted to use a language with more support for functions and string processing. I settled on either Lua and Python, and eventually went with Lua. Lua is a dynamically typed language, which is designed to be embedded in C programs. This was the tipping factor for me, I'm curious to see if there are any useful use cases for Lua in future projects. I've heard you can do the same with Python, but that it can be difficult.

For this project, I used Lua solely as a stand-alone interpreter, rather than embedding my Lua scripts in a C program. My first task was to learn Lua. I spent a morning reading the Lua reference manual, which was accessible and easy enough to get through. One of the interesting quirks of Lua is that it uses a primitive type table as the only way to implement arrays and dynamic structures!

Tables are relatively straightforward, and the language provides built-ins to manipulate the tables. I found two surprises while working with tables: first, tables are one-indexed by default (rather than zero-indexed like C arrays); and second, nil values cannot be added to tables. However, tables are extensible types, and one can use metatables to define how operations, like <, work on tables. This could be important, since there is no default way to compare two tables. Adding elements to tables is easy with the table.insert function, which by default appends to the table, but can also be used to insert relative to a table element. The table.sort operation takes a function as its second argument that defines the less than operation to use for the sort. table.concat was another useful function, which converts a table to a string, and adds an optional delimiter between each entry of the table. For example,

table.concat(t, ", ")))

converts t to a comma-delimited string.

The last function that was really helpful (and non-obvious) is unpack, which returns the elements of a table as a "list", which can be used as a varargs argument to a function. For example, I found some code to implement the map function:

function map(f, ...)
  local function helper(f, n, a, ...)
    if n > 0 then return f(a), helper(f, n-1, ...) end
  end
  return helper(f, select('#', ...), ...)

end

Which I used to convert a table to a list of numbers to pass as argument to a least common multiple function that I wrote in order to determine the length of a hyperperiod:

function get_hyperperiod_length(task_periods)
  lcm(map(tonumber,unpack(task_periods)))

end

My implementation of lcm is not particularly efficient, but it is also illustrative:

function lcm(...)
  local last_v = 1
  local last_m = 1

  for _, v in ipairs({...}) do
    local m = lcm_2(last_v, v)
    last_m = lcm_2(m, last_m)
    last_v = v
  end
  return last_m

end

Note that for x, y in ipairs(T) defines an iterator over T, where x is the key (index) and y is the value T[x]. In the lcm function, I convert the varargs argument to a table (which would discard nils!) and iterate over it. Most of the functions I wrote make use of the ipairs method to create an iterator to process a table.

My script starts by parsing its arguments, which take the form -T d,e,p or -A d,e,r; T indicates a periodic task, and A indicates an aperiodic task. d is for deadline, e is for execution time, and r/p is for release time/phase. The parameters are used identically, but I need to differentiate between periodic tasks, which are used to compute the slack table, and aperiodic tasks, which are included only because the script will generate the parameters needed to run the aperiodic task in the RTEMS test program.

tasks = parse_args(arg)

Next, the script sorts the tasks, so that periodic and aperiodic tasks can be differentiated:

table.sort(tasks, task_lt)

where task_lt is a function that defines how to compare the strings held in the table tasks, extracted by parse_args.

The script then splits the tasks table into aperiodic and periodic tasks:

periodic_tasks = get_periodic_tasks(tasks)
aperiodic_tasks = get_aperiodic_tasks(tasks)

Then the hyperperiod length is computed, and the jobs in a hyperperiod are generated by taking the task periods and generating jobs for each period until the hyperperiod is reached:

periods = get_deadlines(periodic_tasks)
hyperperiod_length = get_hyperperiod_length(periods)
J = get_jobs(periodic_tasks, hyperperiod_length)

All of the jobs of a hyperperiod are in J, which is a sorted table of tables, where the table at J[i], i = 1 to n, has entries J[i][1] = deadline of job i, J[i][2] = execution time of job i, and J[i][3] = release time of job i. The table is sorted by earliest deadline, with ties broken by earliest release. Now the script can compute the slack:

compute_initial_slacks(J)
slack_table = compute_slack_table(J, hyperperiod_length)

And finally, the script generates a C header file which the RTEMS test program will #include in order to get the task parameters:

write_header(aperiodic_tasks, periodic_tasks, J, slack_table, hyperperiod_length)

The write_header function makes a lot of use of the string.format function, which acts like sprintf (only safer!), and the table.concat function to generate comma-delimited array initializer lists from tables.

An example execution is:

lua gen-slack-header.lua -T 6,1,0 -A 100,5,4 -T 12,1,0

Which generates parameters for two periodic tasks, period (relative deadline) of 6 and 12, and with execution time of 1 and phase of 0. Parameters for an aperiodic task with deadline 100, execution time of 5, and release time of 4 are also generated. This is what the resulting C header file looks like:

 /* slackparams.h
 *
 * This is a generated file.
 * Use the gen-slack-header.lua script to create this file.
 */

#ifndef __SLACKHEADER_H_
#define __SLACKHEADER_H_

#define  TABLE_SIZE                 (6)
#define  JOBS_PER_HP                (3)
#define  HP_LENGTH                  (12)
#define  NUM_PERIODIC_TASKS         (2)
#define  NUM_APERIODIC_TASKS        (1)
#define  NUM_TASKS                  ( NUM_PERIODIC_TASKS + NUM_APERIODIC_TASKS )

/* pre-computed slack table */
uint32_t  slack_ticks[TABLE_SIZE]   = { 5, 5, 5, 9, 9, 9 };
/* slack_table gets converted from ticks to timestamp later */
Timestamp_Control slack_table[TABLE_SIZE];

uint32_t  jobs_per_hyperperiod      = JOBS_PER_HP;
uint32_t  periodic_tasks            = NUM_PERIODIC_TASKS;

rtems_task_priority Priorities[1+NUM_TASKS]= { 0, 6, 12, 100 };

uint32_t  Periods[1+NUM_PERIODIC_TASKS]    = { 0, 6, 12 };
uint32_t  Periods_us[1+NUM_PERIODIC_TASKS] = {
    0*CONFIGURE_MICROSECONDS_PER_TICK,
    6*CONFIGURE_MICROSECONDS_PER_TICK,
    12*CONFIGURE_MICROSECONDS_PER_TICK
                                             };

uint32_t  Tick_Count[1+NUM_TASKS]           = { 0, 1, 1, 5 };
uint32_t  Execution[1+NUM_TASKS]           = { 0, 1, 1, 5 };
uint32_t  Execution_us[1+NUM_TASKS]        = {
    0*CONFIGURE_MICROSECONDS_PER_TICK,
    1*CONFIGURE_MICROSECONDS_PER_TICK,
    1*CONFIGURE_MICROSECONDS_PER_TICK,
    5*CONFIGURE_MICROSECONDS_PER_TICK
                                             };

uint32_t  Phases[1+NUM_TASKS]           = { 0, 0, 0, 4 };
uint32_t  Phases_us[1+NUM_TASKS]        = {
    0*CONFIGURE_MICROSECONDS_PER_TICK,
    0*CONFIGURE_MICROSECONDS_PER_TICK,
    0*CONFIGURE_MICROSECONDS_PER_TICK,
    4*CONFIGURE_MICROSECONDS_PER_TICK
                                             };

#define build_task_name() { \
Task_name[ 1 ] =  rtems_build_name( 'P', 'T', '1', ' ' );\
Task_name[ 2 ] =  rtems_build_name( 'P', 'T', '2', ' ' );\
Task_name[ 3 ] =  rtems_build_name( 'A', 'T', '3', ' ' );\
}

#endif

Read More