How to Track Non Atomic Data Types

In general, processes do not execute atomically, since the operating system may interrupt processes between essentially any two instructions, allowing other processes to run. If your application's process is not prepared for these interruptions, another process may be able to interfere with it, causing the data structures to end up in inconsistent states if arbitrary code is executed between them.

A non atomic condition is a vulnerability to interference caused by untrusted processes. These are conditions caused by processes running other, different programs, which introduce other actions between steps of the program. These other programs might be invoked by an attacker.

This use case illustrates how to use Ocular to analze for non atomic data types, using the FreeRTOS real-time operating system kernel as the example target application.

Downloading the FreeRTOS Application

Download the FreeRTOS application and unzip the source code into the Ocular subjects directory, for example subjects/FreeRTOS.

Creating the FreeRTOS Application CPG

importCpg("subjects/FreeRTOS")

FreeRTOS's CPG is automatically loaded into memory and your workspace.

Declaring an Array of Primitive Types

val primitiveTypes = List("int", "float", "double", "void", "size_t", "ANY", "void", "char", "short")

Calling a Convenience Function to get LineNumber

def getLineNumber(ln : Option[Integer]) = (ln match { case Some(x) => x ; case None => 0 }).asInstanceOf[Int]

Declaring a Data Structure of User Defined Types

case class UDT(uType : String, uName : String,  methodName : String, fileName : String, lineNumber : Integer)

Acquiring all Identifiers into UDT Data Structure

Negative filter on primitive types.

val udtList = cpg.identifier.l.map {
   i => UDT(i.typeFullName, i.name, i.start.method.name.l.head, i.start.file.name.l.head, getLineNumber(i.lineNumber))
} filter {
   p => !primitiveTypes.exists(e => p.uType.contains(e))
} distinct

Storing Findings in a Multimap Keyed by Identified methodName

import collection.mutable._
val udtMap = new HashMap[String,Set[UDT]] with MultiMap[String,UDT]
udtList.foreach { 
item => udtMap.addBinding(item.methodName, item)
}

Storing Findings in a Multimap Keyed by Identified Type

import collection.mutable._
val udtMapByType = new HashMap[String,Set[UDT]] with MultiMap[String,UDT]
udtList.foreach { 
item => udtMapByType.addBinding(item.uType, item)
}

implicit def flat[K,V](kv: (K, Option[V])) = kv._2.map(kv._1 -> _).toList

Calling a Convenience Function to get Range Given Start and End

def getRange(start : Int , end : Int) = start to end toList

Giving functionName Return all callOuts within Scope of the Function

def getCallOutDetails(fnName:String) = cpg.method.name(fnName).callOut.l.map(co => (co.name , getLineNumber(co.lineNumber))).sortBy(_._2)

Optimizing Name Replacement

def getCallOutDetails(fnName:String) = cpg.method.name(fnName).callOut.l.par.map(co => (co.name , getLineNumber(co.lineNumber))).toList.sortBy(_._2)

Calling a Convenience Function for Holding Functions with CRITICAL SECTIONS with Ranges

case class WithCriticalSection(fnName : String, fileName : String, csRange : List[(String, Int, Int)])

Specifying Functions to Optimize Ranging

For situations in which multiple critical sections exists in a method (function).

def getBounds(dataTuples : List[(String,Int)]) =
  dataTuples.foldLeft((List.empty[(String, Int)], Option.empty[(String, Int)])) {
    case ((state, previousSignal), signal) =>
      if (previousSignal.exists(_._1.contains("EXIT")) && signal._1.contains("EXIT")) {
        (state.dropRight(1) :+ signal, Some(signal))
      } else {
        (state :+ signal, Some(signal))
      }
  }

def getRange(enterExits : (List[(String, Int)], Option[(String, Int)])) =
  enterExits._1.foldLeft(
      (List.empty[(String, Int, Int)], Option.empty[(String, Int, Int)])) {
      case ((state, accSignal), signal) =>
        if (signal._1.contains("ENTER")) {
          (state, Some(("CRITICAL_SECTION_RANGE", signal._2, 0)))
        } else {
          val enterExt = accSignal.map(elem => elem.copy(_3 = signal._2))
          (state :+ enterExt.get, Option.empty)
        }
    }._1

Getting Entire callOut Trace for Each Method that Encompasses taskENTER_CRITICAL

val callMap = cpg.method.filter(_.callOut.name("taskENTER_CRITICAL")).l map {
  s => Map(s.name -> (s.start.file.name.head, getCallOutDetails(s.name.replaceAll("\\*",""))))
} reduce(_ ++ _)

Getting Entire callOut Trace for Each Method that DOES NOT Encompass taskENTER_CRITICAL

val callMapWithoutCS = cpg.method.filterNot(_.callOut.name("taskENTER_CRITICAL")).l map {
          s => Map(s.name -> (s.start.file.name.headOption.getOrElse("NOT_IDENTIFIED"), getCallOutDetails(s.name.replaceAll("\\*",""))))
        } reduce(_ ++ _)

Optimizing Replacement

def timeTaken[R](block: => R): R = {
    val t0 = System.nanoTime()
    val result = block    // call-by-name
    val t1 = System.nanoTime()
    println("Elapsed time: " + (t1 - t0) + "ns")
    result
}

val mWithoutCS = cpg.method.filterNot(_.callOut.name("taskENTER_CRITICAL")).l

timeTaken {
   val callMapWithoutCS = mWithoutCS.map {
         s => Map(s.name -> (s.start.file.name.headOption.getOrElse("NOT_IDENTIFIED"),  getCallOutDetails(s.name.replaceAll("\\*",""))))
   } reduce(_ ++ _)
}

Filtering callMap and Fitting into WithCriticalSection

val callMapFiltered = callMap map {
    case(k,v) => k -> (v._1 , getRange(getBounds(v._2.filter(t => t._1.contains("taskENTER_CRITICAL") || t._1.contains("taskEXIT_CRITICAL")))))
} map { case(k,v) => k -> WithCriticalSection(k,v._1,v._2) }

Navigating using an Identifier

For example called xQueueAddToSet. Pick any type from udtMapByType say for instance tfp_format.

…
"SIZEOF_LONG_LONG" -> Set(
    UDT("SIZEOF_LONG_LONG", "lng", "tfp_format", "../../Downloads/dahling-fw/Src/utils/tinystdio.c", 398),
    UDT("SIZEOF_LONG_LONG", "lng", "tfp_format", "../../Downloads/dahling-fw/Src/utils/tinystdio.c", 412),
    UDT("SIZEOF_LONG_LONG", "lng", "tfp_format", "../../Downloads/dahling-fw/Src/utils/tinystdio.c", 408)

...

val nonAtomicUsedInCS =callMap.getOrElse("tfp_format","NOT_FOUND")
val nonAtomicUsedInNoCS =callMapWithoutCS.getOrElse("tfp_format","NOT_FOUND")

If (nonAtomicUsedInCS.size > 0 && nonAtomicUsedInNoCS.size > 0), this implies that a non atomic data type is used both in guarded context and not in guarded context, possibly leading to deadlock or starvation.

Determining the Location Details of Where the Non Atomic Data type is Used

val udtSet = udtMap("xStreamBufferReset")
val callSiteData = callMapFiltered.get("xStreamBufferReset").get

udtSet.foreach {
  udt => callSiteData.csRange.map { item => 
    if((udt.lineNumber > item._2) && (udt.lineNumber < item._3)) {
      printf("[%s] is bound in critical section at [%d] between [%d] and [%d] in methodName [%s] located at [%s]\n", udt.uName, udt.lineNumber, item._2, item._3, udt.methodName, udt.fileName)
    }
  }
}