We continue discussing the paper "Shielding applications from an untrusted cloud with Haven,” written by Andrew Baumann, Marcus Peinado, and Galen Hunt. Today we review the SGX Limitations and workarounds.  There were three main limitations encountered. These were in addition to the need for dynamic memory allocation that unmodified applications required. Together these limitations were hard enough to prevent the unmodified applications to run. Therefore SGX needed to be revised. The paper mentions workarounds for these limitations. They are :
Exception handling, Permitted instructions and Thread-local storage. SGX allows an enclave to handle its own exceptions by reporting the exception cause and register context securely. But the exceptions are not always reported to the enclave. Hardware interrupts were not reported because they divulged private information about the host. The list of reported exceptions included program faults such as division by zero, breakpoint instructions, and undefined instructions, and floating point/SIMD exceptions, but not page faults or general protection faults. This prevented the enclave from handling these faults without trusting the host. But faults such as page faults are handled in user mode code. SGX was therefore revised to report these faults to the enclave.
The permitted instructions prohibits in-enclave execution of instructions that may cause VM exit or change software privilege levels. But three of these instructions are commonly encountered in applications and LibOS. These are CPUID, RDTSC and IRET. The first one queries processor features to test for extended instructions. It is prevented because a VM may trap and emulate it. However emulation doesn't work because the enclave's registers are not visible to the hypervisor. Haven worksaround it by emulating CPUID in its exception handler with static knowledge of features available on SGX. The second instruction return the cycle counter and are used as timestamps. SGX prevents it, because like CPUID, they may cause a VM exit but unlike CPUID, they may cause a VM exit. SGX was revised to permit it if VM exit is disabled. IRET is an interrupt return and it is used at the end of an exception handler when restoring processor state. It is disallowed because it can change protection level. Haven worksaround it by emulating IRET. The third limitation stems from legacy architectures such as x86 using FS or GS segments from Thread control structures (TCS) but TCS is immutable once created. This prevented user mode scheduling in shield module. Haven worksaround it by mapping application threads 1:1 onto TCSs and host threads. Revised SGX has addressed this limitation.
#typewritermonkey problem
A typewriter consists of K keys from the upper case English alphabets with repetitions.  A monkey can type one letter at a time to make a string of length S. A target word of length L can appear many times in the output. The monkey can get paid one banana for each word. If you bring as many bananas such that you will not run out, how much can you expect to keep.
The solution here is to find the max and the average of the number of success. The max is say S-L+1 bananas if all the letters of the target word are in the K keys.  The average depends on the sum total of all possible successes and varies from case to case depending on what S and L are or can be taken as probability. Given the keys on the keyboard and the target word spelled out, we can choose each letter with the probability depending on the number of times it appears in K. Multiplying each letter with its probability for each of L elements gives the total probability.

We continue discussing the paper "Shielding applications from an untrusted cloud with Haven,” written by Andrew Baumann, Marcus Peinado, and Galen Hunt. We were discussing the initialization step for the shield module.After initialising itself, the shield generates a public/private key pair, and then uses its parameters to establish a network connection with the user. The connection is made to a machine physically under the control of a user or another enclave in the cloud. In either case, the shield uses the SGX attestation mechanism to create a hash and sends it to the user along with its public key. This proves that the shield has correctly loaded and executes in an SGX enclave. If the enclave's measurement is as expected which means the shield was correctly loaded with the desired parameters, the user encrypts the VHD key using the public key sent and sends it back. Therefore any tampering with the shield binary is detected and thwarted. The shield now decrypts the VHD key using its private key and uses it to access the contents of the VHD. With this the LibOS and application can be loaded and any communication with the outside world and access to secrets in the VHD is controlled by the application. The network connection is over SSH and the keys may be stored in the VHD itself to begin with. The connection can therefore be made over the untrusted network but this could be extended to using virtual private network.
After initialization and loading, the application performs most of its execution in the enclave, calling out to the untrusted host only for system services. This is opposite of the SGX usage model of untrusted code calling into an enclave The upcalls are performed with EENTER and the downcalls are peformed with EEXIT, the latter with proper cleanup.
#codingexercise.
Usually one can reach a number starting from 1 by incrementing 1 repeatedly.
But assume the following operations are permitted:
1) a number can be reversed to speed it up. For example after 12, comes 13 and 13 can be reversed as 31 and the next number can be 32
2) a number can reversed to decrement as well. For example 10 can be reversed to 01 and the leading zeros removed to get 1.
Find the minimum number of operations to be performed (or  the different numbers generated) to arrive at a given number N.
Solution: Note that the speedup is what we want for minimal number of numbers. The speedup happens only when the reverse of the number is less than the destination. For example to reach 33, we have to count uptil 13 and then invert to get 31 followed by unit increments to 33. The  speedup happens best when the reverse that gets you  the largest jump.
For example, we can to get 100, we can go 1 to 19, then invert it to get 91 and increment to 100 resulting in 29 interim numbers
or we could go from 1 to 18 81 through 89 and 98 to 100 = 30 numbers
1 through 15 51 through 59 95 through 100 = 29 numbers
1 12, 21 through 29, 92 through 100 = 29 numbers
1 12, 21 through 25, 52 through 59, 95 to 100 = 30 numbers
Note that the solution is incremental as well and the sequence generated will be the same for each increasing N.
what sequence was generated for 97 will also be generated for 98 and will work for 99  because either the reverse is chosen or the next increment is chosen at each step resulting in a strictly increasing sequence. So we can generate each numbers predecessor and this will always be the same.

index   0 1 2 3 ... 9 10 11 12 13 .. 21
current 0 1 2 3 ... 9 10 11 12 13 ...13
we start with an array of sequential numbers to N starting from 0.
int GetNext(int[] A, int index)
{
  int next = A[index-1] + 1; // next increment by default
  int r = ReverseInt(index);
  if (index % 10 != 0 and r < index )
        next = min(A[index], A[r]+1);
        A [index] = next;
  return next;
}

When iterated from 1 to N, the GetNext fills the array A and the desired answer can be directly read from the array at the index corresponding to the number.

We continue discussing the paper "Shielding applications from an untrusted cloud with Haven,” written by Andrew Baumann, Marcus Peinado, and Galen Hunt. We were discussing user mode scheduling by shield module.In order to generate entropy for the shield, a RDRAND instruction is used which is a secure source of randomness. It uses this together with dynamic loading/relocation of application binaries. Our loader space does not yet implement address space layout randomization. Process creation is not supported. Very few applications fork process on Windows. and those that do often run it as a subprocess. It is often sufficient to run the subprocess in a different portion of the parents address space.within the enclave.
Haven applications are deployed using Cloud VMs, with an extra attestation step we now describe. A user constructs a disk image containing application and LibOS binaries and data, and then encrypts it without sharing its key. The encrypted VHD and shield binary are sent to the cloud provider. The shield is not encrypted but its integrity will be verified. The cloud provider establishes a picoprocess and loads the untrusted runtime. When the enclave is created, it loads the shield module. While the shield is loaded, the hardware attestation mechanims compute the hash for the initial state. The shield receives two startup parameters, a structure of untrusted parameters chosen by host and a structure of trusted parameters chosen by the user. The host chooses addresses of down call functions and the user chooses configuration options such as the environment variables. This makes up the initialization step.
#codingexercise
 A grid of R rows and C columns contains one of the four directions or nothing. Assume that a pegman dropped on the grid will start using the direction in the cell and continues to move in that direction across empty adjacent cells. If the pegman is dropped on an empty cell, he stands still forever. If the pegman encounters another direction, he will change direction as per the new one. Given that there are only a few directions present on the grid and we can only change existing pattern, find the minimum number of directions, if any, that can be changed to prevent the pegman from falling off the board.
Solution: The best way to prevent the pegman from falling off the board is when there is another direction between its current and the boundary. Because that direction can be changed as opposite to the current and the pegman can be bounded forever. The four directions can be arranged in two by two grid as going around the perimeter clockwise to give an example of retaining it within a board.

int getCount(int[,]grid, int r, int c, int deltar, int deltac, Dictionary<char, Tuple<int,int>> directions)
{
int count = 0;
for (int i = 0; i < R ; i ++)
   for (int c = 0; c < C; c++)
   {
        if (grid[r,c] == '.') continue;
        Tuple<int, int> delta = directions[grid[r,c]]; // generates +/- 1, +/- 1
        if (nextDirExists(grid, r, c, delta.Item1, delta.Item2)) continue;
        bool solution = false;
        foreach (var kvp in directions){
               delta = kvp.value
               if (nextDirExists(grid, r, c, delta.Item1, delta.Item2))
               {
                      solution = True;
                }
        }
        if (solution){
             count += 1;
         }
    }
return count;
}

#problemsolving there are many puzzles that can be made with a grid layout and repeating patterns such as in a chessboard. Often the military uses such signs for their colors on their uniforms. Signals here are formed formed repeating sequences and colors that designate the team and are a way for the identification of that team.

We continue discussing the paper "Shielding applications from an untrusted cloud with Haven,” written by Andrew Baumann, Marcus Peinado, and Galen Hunt. We were discussing memory and storage protection. We were discussing memory and storage where the shield module not only encrypts data but also implements its own filesystem so that disk blocks can be independently encrypted.A Merkle tree protects the integrity of the overall disk. The crypto metadata is stored in separate blocks from the filesystem.A scheme of two hash versions is used to maintain consistency after crashes. Just like memory and storage, the host can also exploit thread scheduling such as by allowing two threads to concurrently acquire a mutex. This is mitigated by a user mode scheduler that the shield module. At startup, a fixed number of threads is created that is configurable. These act as virtual cpus supporting many more application threads inside the enclave.Run queues and synchronization objects are maintained using atomic instructions for safety. The untrusted interface's event and interrupt mechanisms support suspending/resuming and signalling the virtual cpus. The shield does not support process creation. With Windows OS, very few applications fork a new process and even when they do the subprocess can be  run in a different portion of the parents address space.
#codingexercise
Given a 2D array of R rows and C columns filled with N elements such that inner walls within the array have fewer elements on either side, find the number of such walls that that have elements on both sides
we mentioned the solution and sample code earlier. Today we implement counting the number of inner walls that have occupancy on both sides.
bool getCountInnerWalls(int[,] used, int row, int col)
{
int count = 0;
for (int i = 0; i < row-1; i ++)
  for (int j = 0; j < col-1; j++)
  {
     if (used[i,j] && used[i,j+1]) count ++;
     if (used[i,j]  && used[i+1,j]) count++;
   }

for (int j =0; j < row-1;  j++)
{
if (used[row-1,j] && used[row-1, j+1]) count++;
}
for (int i =0 ; i < col -1; i++)
{
if (used[i,col-1] && used[i+1, col-1]) count++;
}
return count;
}

We continue discussing the paper "Shielding applications from an untrusted cloud with Haven,” written by Andrew Baumann, Marcus Peinado, and Galen Hunt.  We were discussing the Drawbridge ABI and the untrusted runtime. Let us look at the services provided by the shield module. The virtual address region occupied by a Haven enclave starts at zero. This allows the enclave to reliably detect and handle NULL pointer dereferences. A malicious host could map pages there and redirect NULL access to choice data. Hence a check is performed at startup that the address starts at zero, The enclave's virtual size must be large enough for all possible allocations by application and small enough to leave some for the untrusted runtime and host OS. The shield manages virtual memory within the enclave. It includes a region allocator, tracking the sub-regions of the enclave. Regions, pages and allocations are hierarchical and the shield which are committed and usable by the application and their permissions (read, write, execute). For each allocation, the shield chooses an address, calls out to the host to make appropriate changes, then uses the dynamic memory allocation instructions to ensure that the expected changes are made. By going in the middle, the shield never allows the host  to  choose virtual address space and prevents exploits of the latent bugs in the application. If the application requests non-enclave memory, it suitably blocks and fails the request.
Data is protected by encryption when its in memory and when it is in secure persistent storage. The encryption alone doesn't work in storage because the file metadata may leak guest state. That is why shield implements a private file system. The prototype that the authors built uses a FAT32 file system on an encrypted VHD image. Each disk block is encrypted independently.
#codingexercise
Given a 2D array of R rows and C columns filled with N elements such that inner walls within the array have fewer elements on either side, find the number of such walls that that have elements on both sides
we mentioned the solution earlier, today we implement traversing the alternate concentric border starting at (i,j) the top left and with length row and height col but we pick out the corners before calling this method.
bool traverseAlongBordersAndPlace(int[,] used, int i, int j, int row, int col)
{
for (int y = j; y < j + col; y++)
     if (used[i,y] == 0) { used[i,y] = 1; // occupied
         return True;}

for (int x = i; x < i + row; x++)
     if (used[x,j+col-1] == 0) { used[x,j+col-1] = 1; // occupied
          return True;}

for (int y = j+col-1; y >=j ; y--)
     if (used[i+row-1, y] == 0) { used[i+row-1,y] = 1; // occupied
          return True;}

for (int x = i+row-1; x >=0 ; x--)
     if (used[x,j] == 0) { used[x,j] = 1; // occupied
          return True;}
        return False;
}

We continue discussing the paper "Shielding applications from an untrusted cloud with Haven,” written by Andrew Baumann, Marcus Peinado, and Galen Hunt. We were discussing how Haven mitigates lago attacks from a malicious host by narrowing down the OS calls, implementing a user mode runtime and by checking the parameters and return values of calls. In the event of an attack, the shield handles incorrect host behavior by panicking. It emits a short debug message, requests the host to terminate its process, and rejects subsequent attempts to enter the enclave. The interface at the enclave boundary that checks the correctness of all operations also enables a policy/mechanism separation. The guest controls policy for virtual resources ( virtual address allocation, threads, etc.), while the host manages policy only for physical resources (e.g. memory and CPU time). This is a classic design pattern that lets the host govern the state and restricts it to resource allocation and release. Since the host is responsible only for the physical resources, attacks and surface area is significantly reduced. Besides it takes the volatility out of the host, while enabling those changes with easy to modify policies by the guest. The policies can all be dropped and reloaded  at will while the server keeps track of only its state. The server doesn't even need to keep track of the changes to the allocations because policies can be dynamically mapped to resources. The combination of policy with the mechanism complement each other for the resource management.In this case, the implementation and verification becomes even more efficient with a minimalistic interface that is expressed as Drawbridge ABI. Specifically, this interface provides the following operations:
it calls to commit, free and protect specific page,
it manages threads and signals
it performs I/O streams to access untrusted storage and network and
it is a source of system time.
Haven augments the Drawbridge  ABI with this untrusted interface and an untrusted runtime outside the enclave. This runtime creates the enclave, loads the shield and forwards calls between the enclave and the host OS.

We continue discussing the paper "Shielding applications from an untrusted cloud with Haven,” written by Andrew Baumann, Marcus Peinado, and Galen Hunt. Today we discuss Haven design that extends the Drawbridge. The shield module implements the Drawbridge ABI which the LibOS requires. The LibOS provides a limited subset of core OS functions.The shield module provides a user mode implementation of memory management, file system, thread synchronization . It emulates the operating system and acts as a trusted bootloader for the LibOS and the application. It mitigates lago attacks from outside the enclave. It does this by validating all parameters and results passed across a narrow interface with the untrusted runtime. For example it validates that the parameters of upcalls and the results of the downcall agree with their specification. Many OS call parameters take buffer and size and validations include the check such as the number of bytes read cannot be more than the requested size. Similarly error codes must be within an acceptable list for specific downcalls. Both hardware and software can be leveraged to perform additional validation.
#codingexercise
Given a 2D array of R rows and C columns filled with N elements such that inner walls within the array have fewer elements on either side, find the number of such walls that that have elements on both sides

Solution. The boundaries are the starting points and that too the corners followed by alternate penultimate boundary of elements until the center and then the rest .The walls of the boundary can be enumerated as vertical as to the right of the element or horizontal as below the element leaving those walls that are on the boundary the horizontal floors of the last row and the vertical floors of the last column. If a wall has elements on both sides, it is counted. The count of these walls is returned.