Category Archives: programming

Zero, One, Else

Sometimes, there are only three numbers that matter.

Stepping from Zero to One is when a componet is being introduced. Stepping from One to Zero is when a component is being elliminated. From these systems engineering processes, the latter is preferred, but the former is the reality. Still, these two processes are usually well defined, and are driven by functionality.

The Else is the realm of non-functional requirements, the gate through which scalability problems enter the scene. Even if Else is only 4. Tomorrow it may grow to 57.

The Else is where concurency becomes a problem. The Else is where one should decide which way to scale – up or sideways. The Else is when no one can speak for sure without referring to historical data. The Else is the 2 am call when all is down and nothing works because memory was upgraded, and cache miss ratio is in the sky

Stack traces on Linux/x86

While reading stackoverflow I recalled a little snippet I wrote 4 years ago.

This snippet allows the programmer to get a stack trace in C environment on Linux/x86 whenever a memory access problem happens. x86_64 is not supported yet.


/* */
#include <stdio.h>
#include <stdlib.h>

#include <signal.h>

#include <execinfo.h>

#include <unistd.h>

#define __USE_GNU
#include <ucontext.h>

typedef void signal_specific_handler(int signum, siginfo_t *pinfo, void *arg) ;

struct sigaction_pack
{
 struct sigaction         current ;
 struct sigaction         original ;
 signal_specific_handler *pspecific ;
} ;

/* we are instrumenting the first 32 signals. We are NOT instrumenting the real-time signals */
static struct sigaction_pack g_pbs_signal_actions[32] ;
static size_t max_pbs_size = 32 ;

static void* g_a_activation_record_list[64] ;
static size_t max_activation_record_count = 64 ;
static size_t activation_record_count ;

/* This is a global variable set at program start time.  It marks the  highest used stack address.  */
extern void *__libc_stack_end;

/*------------------------------------------------------------------------------
 *
 *   A short refresh on the x86 assembly
 *   -----------------------------------
 *
 *    %eip -> current instruction
 *
 *    %esp -> top of the stack (the used element)
 *
 *   This is the stack layout we see with every stack frame.
 *
 *           +-----------------+
 *   %esp -> | local variable  |
 *           | local variable  |
 *           +-----------------+
 *   %ebp -> | %ebp last frame |-+
 *           |                 | |
 *           | return address  | |
 *           |(old instruction | |
 *           |   pointer )     | |
 *           +-----------------+ |
 *           | parameters 1..  | |
 *      +----| parameters 2... |--+
 *      |    | parameters---   |
 *      |    +-----------------+
 *      |    | local variable  |
 *      |    | local variable  |
 *      |    +-----------------+
 *      + -> | %ebp last frame----....
 *           |                 |
 *           | return address  |
 *           +-----------------+
 *
 *
 */

/**
 * Activation record layout
 * Used to parse stack contents while unwinding the stack.
 */
struct activation_record_layout
{
 struct activation_record_layout * next;
 void *return_address;
};

/**
 * Unwind the stack at any location.
 * This function works like the backtrace function provided by the GNU libc,
 * with the only difference that this function doesn't unwind _current_ stack.
 * Instead, it takes values of the relevant registers (EIP, EBP and ESP) as
 * parameters.
 * Thus, this function is suited for being called from a signal handler.
 */
int
rhyno_backtrace (
   void **activation_frame_array,
   int    max_size,
   void  *eip,
   void  *ebp,
   void  *esp)
{
 /* used to parse the stack */
 struct activation_record_layout *current;

 /* keeps track on visited stack trace */
 int count = 0;

 /* save the EIP into the frames list */
 activation_frame_array[count++] = eip ;

 /* Initialize the frame list with EBP */
 current = (struct activation_record_layout *) ebp;

 while (count < max_size)
 {
 /* If we reach past stack pointer, or end of stack segment,
 * we have problem (possible memory overrun.)
 */
 if ((void *) current < esp || (void *) current > __libc_stack_end)
 break;

 /* Save the return address of frame i into the frame list */
 activation_frame_array[count++] = current->return_address;

 /* Advance the frame list pointer */
 current = current->next;
 }

 /* How many frames we had collected */
 return count;
}

void sa_segv_specific_hanlder(int signum, siginfo_t *pinfo, void *arg)
{
 /*
 Example for SEGV...
 */
 printf("  Segmentation violation: Reason: %d: %s\n",
 pinfo->si_code,
 pinfo->si_code == SEGV_MAPERR ?
 "Address not mapped" : pinfo->si_code == SEGV_ACCERR ?
 "Invalid permissions" : "?????") ;
 printf("    Offending address: %p\n", pinfo->si_addr ) ;
}

void sa_bluescreen_handler(int signum, siginfo_t *pinfo, void *arg)
{

 /*
 siginfo_t {
 int      si_signo;  / * Signal number * /
 int      si_errno;  / * An errno value * /
 int      si_code;   / * Signal code * /
 pid_t    si_pid;    / * Sending process ID * /
 uid_t    si_uid;    / * Real user ID of sending process * /
 int      si_status; / * Exit value or signal * /
 clock_t  si_utime;  / * User time consumed * /
 clock_t  si_stime;  / * System time consumed * /
 sigval_t si_value;  / * Signal value * /
 int      si_int;    / * POSIX.1b signal * /
 void *   si_ptr;    / * POSIX.1b signal * /
 void *   si_addr;   / * Memory location which caused fault * /
 int      si_band;   / * Band event * /
 int      si_fd;     / * File descriptor * /
 }
 */
 printf("Got deadly signal %d, following information (%p) is available:\n",
 signum,pinfo ) ;

 printf(" Signal %d (code %d, errno %d) send by process %d (uid %d)\n",
 pinfo->si_signo,
 pinfo->si_code,
 pinfo->si_errno,
 pinfo->si_pid,
 pinfo->si_uid ) ;

 /* Call message specific handler.
 For example, the segmentation fault handler will
 print the offending address
 */
 if (g_pbs_signal_actions[signum].pspecific != NULL)
 {
 (*g_pbs_signal_actions[signum].pspecific)(signum,pinfo,arg) ;
 }

 if ( arg == NULL )
 {
 printf("No register/stack information is available\n") ;
 }
 else
 {
 printf("Important CPU Registers:\n" ) ;
 printf("CS:  %012p DS:  %012p  SS:  %012p \n",
 ((ucontext_t*)(arg))->uc_mcontext.gregs[REG_CS],
 ((ucontext_t*)(arg))->uc_mcontext.gregs[REG_DS],
 ((ucontext_t*)(arg))->uc_mcontext.gregs[REG_SS]
 ) ;

 printf("EIP: %012p EBP: %012p  ESP: %012p\n",
 ((ucontext_t*)(arg))->uc_mcontext.gregs[REG_EIP],
 ((ucontext_t*)(arg))->uc_mcontext.gregs[REG_EBP],
 ((ucontext_t*)(arg))->uc_mcontext.gregs[REG_ESP]
 ) ;

 printf("\n\nStack Trace:\n") ;

 /*------------------------------------------------------------------------------
 * Collect activation records in format similar to that of
 * glibc's `backtrace', but use the foreign stack.
 */
 activation_record_count = rhyno_backtrace(
 g_a_activation_record_list,
 max_activation_record_count,
 (void*)(((ucontext_t*)(arg))->uc_mcontext.gregs[REG_EIP]),
 (void*)(((ucontext_t*)(arg))->uc_mcontext.gregs[REG_EBP]),
 (void*)(((ucontext_t*)(arg))->uc_mcontext.gregs[REG_ESP])
 ) ;

 /*------------------------------------------------------------------------------
 * Use internal glibc reporting mechanism to convert
 * activation records to symbolic names (requires -rdynamic linker flag)
 */
 backtrace_symbols_fd(g_a_activation_record_list,activation_record_count,1) ;

 } /* register information */

 /* propagate the signal to the original handler */
 if ( g_pbs_signal_actions[signum].original &&
 (g_pbs_signal_actions[signum].original.sa_sigaction != NULL ))
 {
 printf("\n\nPropagating the signal %d to the original handler\n",
 signum) ;
 g_pbs_signal_actions[signum].original.sa_sigaction(signum,pinfo,arg)  ;
 }
 else
 {
 printf("No original handler is registered for singal %d, continuing\n",
 signum ) ;
 }
}

int register_signal_handlers()
{
 int signum ;
 int result = -1 ;

 for ( signum = 0 ; signum < max_pbs_size ; ++signum)
 {
 /* zero the signal action */
 memset(&g_pbs_signal_actions[signum].current,0,sizeof (struct sigaction)) ;

 /* register the generic handler */
 g_pbs_signal_actions[signum].current.sa_sigaction = sa_bluescreen_handler ;

 /* turn on the flag that tells the runtime to invoke the extended signal handler,
 see man sigaction for details */
 g_pbs_signal_actions[signum].current.sa_flags |= SA_SIGINFO ;

 /* Register the signal handler, store the original signal handler for propagation */
 result = sigaction(signum,&g_pbs_signal_actions[signum].current,
 &g_pbs_signal_actions[signum].original) ;
 /* Report result */
 printf ("-- Registered signal handler for signal %d, result %d, handler %p original handler %p \n", signum,result,
 g_pbs_signal_actions[signum].current.sa_sigaction,
 g_pbs_signal_actions[signum].original.sa_sigaction) ;
 }

 g_pbs_signal_actions[SIGSEGV].pspecific = sa_segv_specific_hanlder ;

 return result ;
}

/* Function prototype. Here we will do THINGS */
int malicious_code(int) ;

int
main (int argc, char* argv[], char* envp[])
{
 int sleep_interval = 300 ;
 /* Very important - register the handlers */
 if ( argc > 1 )
 register_signal_handlers() ;

 sleep(sleep_interval) ;
 malicious_code(10) ;

 return 0 ;
}

int malicious_code(int arg)
{
 if ( ! arg )
 {
 int * garbage_pointer = (int*)441231324;
 return *((int*)(garbage_pointer)) ;
 }
 else
 {
 return malicious_code(--arg) ;
 }
}

Data Leak Prevention and Birthday Attacks

Data Leak Prevention is set of technologies used to monitor information that is leaving corporate network, and taking actions in case sensitive information “leaves the building”. Detection of sensitive information is done usually using pattern matching with checksums (e.g. credit card numbers, which have quite a bit of redundant information for validation), content proximity heuristics (e.g. US social security numbers, which don’t have any redundant information for validation, and without taking content into equation can be recognized as Canadian driver license numbers), digital fingerprints and the combination of the above.

Birthday Attack is a way to meddle with digital signatures to greatly reduce key strength. This attack is based on (and takes its name from) the Birthday Paradox. It resorts to slightly tweaking (by inserting commas, reordering words and using synonyms) two documents – one which is considered to be correct, and one which is not – until both have same digital signature. Once digital signatures collide, one can use the “good” document (e.g. request for a day off) to generate digital signature, and then use “bad” document (e.g. approval for fund transfer) as legitimate. The Birthday Attack reduces key depth by two, effectively turning 64bit digital signatures int 32bit.

Returning to the DLP problem. Usually, corporations have some sort of legal banners, footers, headers and sidebars, which comprise all kinds of disclaimers, terms, conditions and threats. As these are usually not considered sensitive, good fingerprinting schemas will contain “black lists” for “sensitive” fingerprints, along with “white lists” for insensitive fingerprints.

If the potential “extruder” – the person who wants to get the information out from the organization is willing to get away with it – can slightly influence the white lists, he can use the Birthday Attack to mask sensitive bits as legalese, which provide plenty of opportunity for meddling by being inhumanely long and unreadable. Once fingerprint for the sensitive information collide with fingerprint for the legalese, the “extruder” can safely circumvent DLP system.

The DLP system, in order to prevent this kind of attack, should do at least one of following:

  • Disallow meddling with white lists (keep lawyers on track)
  • Use hash functions with sufficient key depth, so that keys will be cryptographically resistant to BA. For example, 2^64 is pretty strong key depth; this suggests that  hash function with key depth of 128 will be used.
  • Combine fingerprints with context information. Seeing one fingerprint from a banner in the middle of neutral text should set some bits on

Autonomous Software, circa 1997

Take your software, put it in a box, throw it out of window.

Sometimes, throwing the software out of the window is not act of frustration. Sometimes, it is just a part of the requirements. In particular, if you put inside the box some tricky hardware, and throw it hard enough, it may reach other planets.

However, one must make sure the software works while being thrown out of window, to reach the final destination.

I am referring, of course, to the Pathfinder project. The Authoritative Account on the infamous software failure is a must read for software engineers.

Unicode Byte Order Detection

Once in a while I run into the following problem: give a stream of bytes, which are know to represent Unicode characters, what is the correct byte order?

Assuming that the Unicode byte stream is valid Unicode stream, we can clearly see that if character Ci is in certain byte order, then the next character, Ci+1 will be in same encoding as well, unless a byte order mark (BOM) specifies the byte order for following bytes.  Moreover, assuming the Unicode byte stream represents character stream, there’s certain probability that adjacent characters belong to same word.

Same words are usually written in same language, which implies same Unicode code page. In other words: in human text, number of different code pages will be low.

This is important property, which we are going to exploit.

This number of different code pages clearly depends on the document: for a math text in English, some words will be in English, some in Greek and some will be special symbols. On the other hand, a biology text in Romanian will include Romanian words intermixed with biology terms in Latin (probably, in italic).

The location of codepage bytes is governed by the byte order used by the Unicode byte stream. By determining, which bytes are used for codepages, we can detect the byte order. 

The algorithm is easy:

  1. take a sampling buffer, _buf  from the stream. The size of _buf should be sufficiently large for detection, but not too large so to slow the algorithm down. 64 bytes sounds like a good guess.
  2. For a first pass: 
    1. Allocate 2 hash sets: LO_BYTE and HI_BYTE
    2. Iterate over the _buf in 2 byte offset increments (stored in offset). Insert _buf[offset] to HI_BYTE and _buf[offset+1] to LO_BYTE 
  3. For a second pass:
    1. Allocate 2 hash sets: LO_NIBBLE and HI_NIBBLE
    2. Iterate over the _buf in 4 byte offset offset. Insert (_buf[offset]&0xFF)<<8|_buf[offset+1]&0xFF to HI_NIBBLE and _buf[offset+2]&0xFF)<<8|_buf[offset+3]&0xFF to LO_NIBBLE 
  4. Chose the hash set best with lowest number of different entries nbest.
    1. if nbest > EXPECTED_NUMBER_OF_LANGUAGES  probably the encoding is UTF8
    2. otherwise, if best is LO_BYTE, the encoding is UTF-16LE 
    3. otherwise, if best is HI_BYTE, the encoding is UTF-16BE
    4. otherwise, if best is HI_NIBBLE, the encoding is UTF-32BE
    5. otherwise, if best is LO_NIBBLE, the encoding is UTF-32LE
    6. otherwise, check your implementation, it probably contains a bug.

Of course, if the BOM (byte order mark) is present, the whole issue of detecting the encoding becomes moot.