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 sandboxing. SGX was designed to protect limited subsets of application logic. Haven makes it usable for unmodified application binaries. This was difficult because applications load code and data at runtime, dynamically allocate and change protection on virtual memory, execute arbitrary user-mode instructions including some not supported by SGX, raise and handle exceptions and use thread local storage. If the application needs to use memory, it is done via LibOS. If the application need to use unsupported instructions, they are emulated. if the application has exceptions from execution. they are validate and handled within an enclave. Haven extends the Drawbridge - a shield module below the LibOS in the enclave and an untrusted runtime outside the enclave. This design implements a shielded runtime in the enclave by calling out to the untrusted host. In fact, this design may apply to LibOS in Linux and not just windows. Both picoprocess and LibOS can be used in Linux with a similar design because the design improves what is available on both platforms for a shielded execution.
#codinginterview
There's a line of B barbers where you have to take a haircut but you are the N'th person standing in a line and the shop has just opened. Each of the barber cuts hair such that the kth barber takes exactly Mk time and doesn't take a break. Mk's are multiples of each other. Which one will cut your hair ?
Answer:
B=2 N =4
M0 = 10, M1 = 5
Answer is 1. First barber.Because at the end of ten minutes three people would have cut their hair and so the next person would go to first barber.
Similarly B= 3 N = 12, M0,..Mk = 7,7,7
Answer is 3 Third barber) Because at the end of seven minutes, three people would have cut their hair and after four iterations, the last barber would have taken the last one.
B= 3 N =8
M0 ..Mk = 4 2 1
Answer is 1 because at the end of four minutes, seven people would have cut their hair and so the next person goes to first barber.
int GetBarber(int B, int N, List<int>M)
{
assert (M.Any(x => x<= 0) == false);
int max = M.Max();
int count = 0;
foreach (int I in M) count+= max/I;
return N%count == 0 ? B : N%count;
}

We continue discussing the paper "Shielding applications from an untrusted cloud with Haven,” written by Andrew Baumann, Marcus Peinado, and Galen Hunt. We discussed instructions with Intel SGX Today we look at the Drawbridge. It is a system that supports low-overhead sandboxing of Windows applications comprising of a picoprocess or library OS.  The picoprocess is an isolation within the hardware address space but with no access to traditional OS services. Instead it uses a narrow ABI of OS primitives using a security monitor. The LibOS is a version of Windows refactored to run as a set of libraries within the picoprocess, depending only on the ABI. It consists of lightly modified binaries for most user-mode and some kernel components of Windows, and a "user-mode kernel" that implements  the interfaces on which they depend. Together they enable sandboxing of the unmodified windows application. This is at par with VM security but with substantially lower overhead. By sandboxing, it is implied that Drawbridge protects the host from an untrusted guest. Complimentary to this Haven shields the execution of the application and LibOS from an untrusted host, thereby enabling mutual distrust between host and guest. Haven is built on instruction level isolation mechanism of Intel SGX. Let us look at how it protects the application from the malicious host OS The first of these is a class of attacks called the lago attacks.  The application makes an assumption that OS will perform correctly. The malicious OS violates this by not only resulting incorrect results from system calls but also seek to expose bugs in the application. The end result is the application crashes but further more sophisticated harm can also be done with such things as data corruption. For example, it may allocate valid but abnormally high virtual addresses., return unexpected error codes from system calls, or simply fail calls that an application naively assumes will succeed. Haven counteracts this by limiting the scope using a LibOS within the enclaveSince the LibOS is under user control, it can be arbitrarily inspected or tested online. Since the LibOS is under user control, and can be arbitrarily tested or inspected offline, it is not malicious. Second with the reduced interface, corrective techniques can be used to implement these OS primitives against a malicious host. This can be done with careful defensive coding, exhaustive validation of untrusted inputs, and encryption or integrity protection of any private data exposed to untrusted code.
#codingexercise
There is a set of sentences appearing below where the letters have been replaced with substitutes. The substitutes are one to one and onto mapped. meaning that the mappings are bidirectional between the meaningful and transformed letters. For example, we are given "a zoo" with letter replacements 'a' with 'y', 'z' with 'q' and 'o' with 'e'  yielding "y qee".  We start out with a meaningful phrase or sentence and we translate to the transformed set. If we are given the following samples, write code to translate any given transformed string.
 ejp mysljylc kd kxveddknmc re jsicpdrysi
rbcpc ypc rtcsra dkh wyfrepkym veddknkmkrkcd
de kr kd eoya kw aej tysr re ujdr lkgc jv
Case #1: our language is impossible to understand
Case #2: there are twenty six factorial possibilities
Case #3: so it is okay if you want to just give up
void Train(string transforms, string actual, ref Hashtable<char, char> h)
{
for (int I = 0; I < transforms.length; i++)
{
  if (transforms[I] != " " && h.ContainsKey(transforms[I]) == false))
 {
           h.Add(transforms[I], actual[I]);
 }
}
}
// q and z may still be missing from Hashtable

string Test(string candidate, ref Hashtable<char, char>h)
{
if (h.Count() != 26)
{
foreach (char c in "abcdefghijklmnopqrstuvwxyz")
{
if (h.ContainsKey(c) == false)
   h.Add(c, "_");
}
}
var ret = new stringbuilder(candidate);
for (int I = 0; I < candidate.length; i++)
{
  if (candidate[I] != " ")
 {
           ret[I] = h[candidate[I]];
}
return ret.ToString();
}

We continue discussing the paper "Shielding applications from an untrusted cloud with Haven,” written by Andrew Baumann, Marcus Peinado, and Galen Hunt. We discussed enclave entry and exit with Intel SGX. We continue with another instruction ERESUME. This comes in useful when there's an exception. Consider the usual working of the OS when an exception occurs. The state of the registers would be saved for later use. When the exception occurs, the context and exception records are created. In Haven, we cannot trust the OS with register state, so the SGX saves the full context and information about the cause of the exit in the thread control structure (TCS) and replaces it with a synthetic context. When the enclave is resumed on the TCS, this entry point must be different from the usual entry and hence the instruction ERESUME is used which restores the last saved context. Alternatively, the OS can re-enter the enclave and this is an opportunity for the OS to inspect and modify its own state. If it doesn't match, an exception can be reported and the enclave must handle it which in this case could be the panic response. SGX is an imperfect implementation of shielded execution. If the OS can see the internal state of the enclave such as the exception vector or in the case of a page fault, the type of access and the base address of the page. It allows the OS to retain control over the resource management i.e CPU time and memory. It can deny service to the enclave but cannot cause it to execute incorrectly. SGX does not allow enclave pages to be added after creation nor EPC permissions changed
We now review dynamic memory allocation. Initially SGX did not allow pages to be added or permissions to be modified. This was limiting for the unmodified applications. Consider the database server as an example that reserves several pages. In SGXv2, there is a co-operative mode between the OS and the enclave by which enclave pages can be added or removed and their permissions modified.
SGX includes additional instructions such as EMODT, EMODPR, EBLOCK, ETRACK and EACCEPT to enable this.
The shield module in Haven works with Drawbridge which is a system supporting low-overhead sandboxing of Windows applications. Drawbridge consists of two core mechanisms, both of which Haven leverages, the pico process and the library OS.  The picoprocess is a secure isolation container constructed from a hardware address space. It does not interact with the OS services or system call. Instead it uses an ABI of a few down calls(40) and even fewer up calls(3).
#codingexercise
An alien language consists of words where every word consists L lowercase letters  and there are exactly D words in the language. However, the letters comprising  the words may have signal loss so we can only represent them as (ab)d(dc) for the L tokens where ab means either a or b and dc means either d or c. and the pattern stands for add, adc, bdd, bdc
We are given L as 3 and D as the following: ["abc", "bca", "dac", "dbc", "cba"]
(ab)(bc)(ca)
int GetCountOfMatchingWords(string pattern, List<string> D, int L)
{
var parts = pattern.split(new char[] {"(", ")"});
var tokens = new List<string>(parts);
tokens = tokens.Where(s => !string.IsNullOrWhitespace(s)).ToList();
assert (token.Count == L);
var results = new List<string> ();
Stringbuilder b;
Combine(tokens, ref results, D, b, 0,0);
return results.Count();
}

Void Combine (List<string> tokens, ref List<string> results, List<string> D, StringBuilder b, int part, int level) 
{ 

   For (int i  = start; i < tokens.Count; i++) 
{
    for (int j = 0; j < tokens[i].Count; j++)
   {  
       If (b.Length == tokens.Count) { if (D.Contains(b)) {results.Add(b);} }
       b[level] = tokens[i][j]; 
       If (I < tokens.Count) 
            Combine(tokens, ref results, D,b, start+1,level+1);
       B[level] = ‘/0’; 
   }
}
} 

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 Intel SGX. SGX protects the confidentiality and integrity of pages in an enclave.  The pages are allocated by the OS but must occupy a specific region of physical memory: the enclave page cache.  Just like the RAM backing it, EPC is a limited resource. Therefore SGX enables OS to virtualize EPC by paging its contents to other storage. While this might be considered risky, the contents of the evicted page are actually written to an encrypted buffer. The OS may relocate this but the hardware keeps a version number for that page and requires the OS to follow a hardware verified protocol to ensure that TLB shootdown has completed.
SGX supports  CPU based attestation by which a remote system can establish shared secrets that allows it to set up an end to end encrypted channel with the enclave. When the enclave is created,  a secure hash known as a 'measurement' is established of the enclave's initial state. The enclave may later retrieve a report signed by the processor that proves its identity to and communicates a unique value (such as a publickey) with another local enclave. Using a trusted quoting enclave, this mechanism can be leveraged to obtain an attestation known as a quote  which proves to the remote system that the report comes from an enclave running on a genuine SGX implementation.
SGX therefore protects the contents and integrity of the memory mappings. SGX also mediates transitions into and out of the enclave using a thread control structure When user code begins executing an enclave, it invokes EENTER on an idle TCS at which point the enclave code might access enclave pages according to the protection model above. This continues in the enclave mode until the user code explicitly leaves by invoking EEXIT or an exception or interrupt returns control to the OS  which is called an asynchronous exit EENTER and EEXIT mark explicit access and they make sure the inputs are validated and there's proper cleanup of registers.
#coding exercise
You are given a store credit of N dollars and a list of prices of different items the store sells. Find the positions of two items on that list that add up to N assuming that there will be a solution in that list.
void printSelections(List<int> prices)
{
var wantedpair = new Hashtable<int, int>();

for (int i = 0; i < prices.Count(); i++)
{
   if (wantedpair.ContainsKey(prices[I])){
          Console.WriteLine("Items at {0} and {1} total N in price", wantedpair[prices[i]], i);
          return;
   }else{
    wantedpair.Add(N-prices[I], I);
   }
}
}
 

#coding exercise
You are given a store credit of N dollars and a list of prices of different items the store sells. Find the positions of two items on that list that add up to N assuming that there will be a solution in that list.
void printSelections(List<int> prices)
{
for (int i = 0; i < prices.Count(); i++)
{
for (int j =0; j < prices.Count(); j++)
{
   if (i != j && prices [i] + prices[j] == N){
          Console.WriteLine("Items at {0} and {1} total N in price", prices[i], prices[j]);
       return;
   }
}
}
}

We continue discussing the paper "Shielding applications from an untrusted cloud with Haven,” written by Andrew Baumann, Marcus Peinado, and Galen Hunt.
We discuss Intel SGX now. SGX protects the confidentiality and integrity of pages in an enclave which is a region of user mode address space. when it is cache-resident,  enclave data is protected by CPU access controls - the TLB but when it is written to memory, it is encrypted and if the data is modified, it will fail to load signaling a fault.
When the enclave is setup, the page mappings are done by SGX and a shadow state for each page is maintained. Enclaves are created by an ECREATE instruction which initializes a control structure in protected memory. Once an enclave is create, pages of memory are added with an EADD instruction. The pages continue to be allocated by the OS but they must occupy a specific region of physical memory - the enclave page cache.  For each EPC page, the hardware tracks its type, the enclave to which it is mapped, the virtual address within the enclave, and permissions (read, write and execute). On each enclave page access, after walking the page table, SGX ensures that the processor is in enclave mode, the page belongs to EPC and is correctly typed, the current enclave maps the page at the accessed virtual address space and the access agrees with the page permissions.

Hybrid puzzles - Layering and Tiling 

In the previous post on puzzle category named Layering we introduced a category of puzzles with an outcome as an overlay of the outcomes of individual puzzles. In another category called Tiling we introduced a category of puzzles that aggregated the results of each puzzle as tiles on a horizontal plane. 

  

Today we combine the layering and the tiling to create a new category called hybrid where the tiles in the plane can be colored as per the color-coding clues given to reveal a part of the picture and the tiles can be rearranged to form a collective picture in that layer. The layers can then be overlaid one on top of the other to reveal the whole composite picture. 

  

This requires the solver to order the tiles horizontally and the layers vertically to reveal the final big picture.  She starts out with unraveling the individual tiles and finishes with the final full and detailed picture Since the tiles need not be square and can even be jig saw pieces, the solver doesn’t necessarily have to interpret the picture revealed in each tile. 

  

We have seen examples of Tiling and Layering in puzzles other than coloring such as  Samurai Sudoku puzzles where two different forms of Sudoku are overlaid one over the other such that the overlap of a common set of tiles help solve both the layers. The example I used however is one which uses color your own jig saw pieces puzzle.

#codingexercise  Find Minimum scalar product of two vectors with co-ordinates x and y respectively.
for eg
     v1 =  1 3 -5
     v2 = -2 4 1
-5 1 3
-2 1 4
Coordinates can be rearranged to form new vectors
    minimum scalar product = -25

int GetMinimumScalarProduct(List<int> v1, List<int>v2)
{
assert (v1.Length == v2.Length); // or pad
v1.Sort();
v2.Sort();
int productsum = 0;

while(v1.Length > 0)
{
// pick one
int vi = v1.First();
if (Math.abs(v1.First()) < Math.abs(v1.Last()))
{
vi = v1.Last();
v1.RemoveAt(v1.Length -1);
}
else
{
    v1.RemoveAt(0);
}

// pick other
if ( vi * v2.First()<= vi* v2.Last())
{
productsum += vi*v2.First();
v2.RemoveAt(0);
}
else
{
productsum += vi*v2.Last();
v2.RemoveAt(v2.Length-1);
}

//repeat
}
return productsum;
}
-3 1 5
-2 1 4

We continue discussing the paper "Shielding applications from an untrusted cloud with Haven,” written by Andrew Baumann, Marcus Peinado, and Galen Hunt. Haven is the first system to achieve shielded execution of unmodified legacy application on commodity hardware. It leverages the hardware protection of Intel SGX (software guard extensions). It defends applications from an untrusted host while not requiring changes to the application. It defends against privileged code such as hypervisor and physical attacks. A cloud user trusts 1) the providers software and hardware, 2) the provider's staff, including system administrators and 3) law enforcement bodies. This is a large and inscrutable trusted computing base.
SGX allows a process to instantiate  a secure region of address space known as an enclave. It then protects the execution of the code even from the host. Haven uses an in-enclave library OS (LibOS) that is derived from Drawbridge. It implements the Windows 8 API using a small set of primitives such as threads, virtual memory and file I/O. Haven implements these primitives using a mutually-distrusting interface with the host OS. This ensures shielded execution of unmodified applications. By pushing against the limits of SGX using unmodified applications, Haven exposed fundamental limitations in SGX which were revised in SGX v2.
#codingexercise
Given a set of M unix paths that already exist and N paths that need to be created, find out the paths that must be given with the default usage of mkdir commands for those that need to be created.
        static void PrintMkdirs(SortedList<string, int> created, SortedList<string, int> todo)
        {
            foreach (var item in todo)
            {
                var parts = item.Key.Split('/');
                string sep = "/";

                for (int i = parts.Length; i > 0; i--)
                {
                    var result = String.Join(sep, parts, 0, i);
                    if (String.IsNullOrWhiteSpace(result) == false)
                    {
                        if (created.ContainsKey(result))
                        {
                            break;
                        }
                        created.Add(result, 0);
                        Console.WriteLine(result);
                    }
                }
            }
        }
#puzzlemaking
In the puzzle category of layering as discussed here and here, we used a vertical collection of puzzle to take a new dimension. Today we discuss tiling. Tiling is also another dimension similar to layering in that it also involves ordering but instead of vertical ordering, here we do ordering on a horizontal plane. To give an instance, consider a picture that is cut up into small squares. This is much like an anagram. Similarly each tile represents a puzzle by itself and when solved, its results can be aggregated and ordered to form a final result. Tiling need not always involve ordering but the position of the tiles helps with solving the puzzle because it's another dimension that throws more light on the current problem. Take for instance Sudoku, it is also composed of tiles where the solution of each subgrid also aids solving the whole grid and vice versa. Most crossword anagrams can also be considered tiles.
The examples I brought up earlier were those involving say coloring where each layer reveals a picture while their collection reveals an overlay that is a bigger or more detailed picture. Its straightforward to do the same with tiles as described earlier.
At the same time tiles come with a property that layering doesn't. As long as tiles fall in place uniquely to represent the final picture, they can take arbitrary shape - be it geometrical like a honeycomb or more cut as jigsaw puzzles. This gives more variation and appeal to how puzzles are laid out. Have you seen a coloring grid where each tile can be colored as per the clues given and then the tiles rearranged to form a whole? The same goes for color-your-own jig-saw puzzles.