We continue discussing the paper "Shielding applications from an untrusted cloud with Haven,” written by Andrew Baumann, Marcus Peinado, and Galen Hunt. We were reviewing Hardware security modules (HSM) and Trusted Hardware  or Trusted Platform Modules(TPM) that isolate applications from an untrusted OS. We also reviewed related work in shielding application from an untrusted OS. However, systems based solely on protecting application memory from an untrusted OS are vulnerable to lago attacks through the system call interface. Systems like InkTag attempt to defeat lago attacks by intercepting system calls but OS systems have a tremendous surface area and this may not handle all that arbitrary applications use.  For example, Linux has over 300 system calls and windows has over 1000 system calls. It also avoids the need for a trusted hypervisor through SGX assistance. Haven mitigates this with a substantially smaller mutually distrusting host interface It also avoids the need for a trusted hypervisor through SGX assistance.
We now look at related work in Cloud Security where systems tackle the problem of removing trust from the cloud One way to do this is to work with encrypted data at rest and in transit. Some database queries and map-reduce programs can take advantage of this and it does not require trusted hardware but new applications have to be written.
There have been some hybrid systems as well. MiniBox combines the isolation of TrustVisor, with the sandbox of NativeClient. Like Haven, MiniBox achieves mutual distrust between application code and the host OS. Unlike Haven, MiniBox relies on a trusted hypervisor, and its isolated execution environment supports only small pieces of application logic, rather than complete unmodified applications. PrivateCore is a virtual machine monitor that implements full memory encryption for commodity hardware. It achieves this by executing guest VMs entirely in-cache and encrypting their data before it is evicted to main memory. Although it relies on a trusted hypervisor, like SGX it builds  a resistance to memory probes and similar physical attacks.
#codejam exercise
Brattleship is played the same as Battleship on a R x C board with a single ship of length W placed horizontally except that the other player can cheat by calling a hit a miss and moving the ship elsewhere but cannot be inconsistent with earlier declarations. How many turns minimum are needed to play ?
int GetMinimumMoves(int R, int C, int W)
{
return R*(C/W) + W - (C%W==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 reviewing Hardware security modules (HSM) and Trusted Hardware  or Trusted Platform Modules(TPM) that isolate applications from an untrusted OS. We were discussing multiplexing TPM systems. There are two approaches here. The first is to multiplex the entire PC between secure kernels and an untrusted OS. However this is slow because it uses a separate chip. The second approach attests a trusted hypervisor or OS. The isolated execution is implemented in software. However, the hypervisor remains under the cloudprovider's control. The cloud provider has to maintain the hypervisor by updating it with patches. The cloud user could compare the TPM attestation with a known hash of the hypervisor binary but the hash has to be meaningful. This can be achieved incrementally even with patches because we take a hash from a good state and as we add patches incrementally, we safeguard the process and the addition, verifying it and regenerating the hash. Essentially the trust between the user and the provider is in the hash. If it is done correctly, it can mitigate tampering. But if it is comprised it lays waste to the efforts. This can be done but the process and mechanism may need to be represented in the hash's meaning.
In other words, with the reasoning above, the authors argue that software alone cannot be sufficient at this time to provide the trusted computing base. Hardware modules are required. Although there are examples such as ARM processors, they too suffer from the same drawback. ARM processors have what is called a 'TrustZone' that enables a secure world execution environment that is isolated from the OS.Hence its very much like the TPM in that it relies on software.
Let us now look into related work in shielding apps from an untrusted OS. Here a number of systems seek to defend applications from a malicious OS. XOMOS used custom hardware or more recently trusted hypervisors. Proxos runs isolated applications on a separate VM, but allows them to interact with  a commodity hardware. Overshadow and SP3 introduced transparent encryption of user memory when visible to the OS and this protects the application data from direct tampering.CloudVisor  extended this technique to full VMs using nested virtualization. On the other hand, SecureME accelerated it in hardware. More recently InkTag optimizes the guest OS and protects persistent storage. Virtual Ghost implements a similar mechanism within the OS kernel.
#codejam and solution
A deer runs around a circle at constant speed. Men are walking along the circle all the time. When a deer catches up with the walker at any time, its called an encounter. The positions and speed of the walkers are given (from 0 to 360 with 0 and 360 treated different and speed in minutes). The deer can change the speed at any time but usually maintains the same rate. What is the minimum number of encounters a deer can have ?
We know that the deer is aware of the starting position D, the number of hikers at that position H and their time to complete the circle as M for all the hikers.
Therefore we can create a list of all positions that can be occupied by repeatedly enumerating the previously added entries in the list with the time increments. If we can find a position in between, then that is sufficient to complete the rest of the hike for the deer. We can evaluate a metric for both dimensions of distance and time using the first two datapoints. If we find the greatest common factors of the remaining distance for the first and the original time taken together with time for each of the 360 starting positions, then this should be greater than the corresponding first component if the second datapoint to avoid an encounter. When we compare the factors, we are essentially converting the circular distance covered to a linear scale and comparing to see that there is some headroom between the two to see that a solution exists without an encounter otherwise there will be at least one encounter. The answer is therefore either 1 or 0.
Courtesy:alexamici 

We continue discussing the paper "Shielding applications from an untrusted cloud with Haven,” written by Andrew Baumann, Marcus Peinado, and Galen Hunt. We were reviewing Hardware security modules (HSM) that isolate applications from an untrusted OS. Another thing that serves this purpose is Trusted Hardware  or Trusted Platform Modules(TPM). TPMs are hardware devices that support a simple attestation mechanism just like in SGX. In more recent versions, it also supports late launch and dynamic attestation of an isolated secure kernel. However there is no support for multiplexing distinct late launch environments. Therefore, TPM systems are multiplexed and this is done with two approaches. The first is to time multiplex the entire PC between security kernels and an untrusted host OS. This approach is slow because it uses a separate chip. The  second approach is to attest a trusted hypervisor or OS, which implements isolated execution in software. However the hypervisor remains under the cloud provider's control regardless of its size. A cloud user may compare a TPM attestation to a known hash of the hypervisor binary, but the provider must be able to update the hypervisor and the user must ultimately trust them. However the attestation that the user receives must be meaningfully connected to a proof of the isolation mechanism.
# codejam codingexercise
Consider a person eating mushrooms from a plate and a cook serving mushrooms on the plate. We can only see the plate every ten seconds and note down the number of mushrooms.  This gives us a sequence of numbers for the mushrooms seen on the plate.
The eater could have eaten in one of two ways:
1) any number of pieces eaten and any number of pieces fed
2) eater eats at a constant rate of some number of mushrooms per second.
If we have a sequence 10 5 15 5, then by the first approach, we have the eater eating 5 then there are 10 more put on plate.then she eats another 10 and there's no way she could have eaten fewer pieces.
And by the second approach eater eats ten pieces in the first ten seconds, 5 more are put on her plate, then she eats for 5 seconds and waits 5 seconds while the plate is empty and then fifteen is put on her plate. She eats ten in the last ten seconds.
Given this sequence, find the number eaten by both approaches.
Tuple<int, int> GetEaten(List<int> numbers)
{
int diff = 0;
var sum = new Tuple<int,int>();
int rate = 0;
for (int i = 1; i < numbers.Count; i++)
{
   diff = max ( numbers[i-1]-numbers[i], 0);
   sum.Item1 += diff;
   rate = max(diff, rate);
}
for (int i = 0; i < numbers.Count; i++)
{
  sum.Item2 += min(numbers[i], rate);
}
return sum;
}

We continue discussing the paper "Shielding applications from an untrusted cloud with Haven,” written by Andrew Baumann, Marcus Peinado, and Galen Hunt.  We discussed SGX optimizations that could be attempted in newer releases but were found in the study by the authors. We continue to review the SGX hardware notes in the paper. We reviewed shielded VMs. We were reviewing Hardware security modules (HSM) that isolate applications from an untrusted OS. Another thing that serves this purpose is Trusted Hardware  or Trusted Platform Modules(TPM). TPMs are hardware devices that are included in many PCs supporting a similar attestation mechanism to SGX. It builds a progressive chain of trust using progressive measurement of code during system boot, such as a bootloader, OS etc. Recent advances have enabled late launch and dynamic attestation of an isolated security kernel. What this does is that it reduces the platform's trusted computing base to just the late launched code which is a form of isolated execution. However unlike SGX, this has two drawbacks:
one it is vulnerable to relatively simple hardware attack including memory snooping and two it lacks support for efficient multiplexing of late launch environments.
#codingexercise
A singer performs for an audience on the stage. The crowd has to be made standing ovation with every audience member standing up and clapping their hands for her.
Initially, the entire audience is seated. Everyone in the audience has a shyness level. An audience member with shyness level Si will wait until at least Si other audience members have already stood up to clap, and if so, she will immediately stand up and clap. If Si = 0, then the audience member will always stand up and clap immediately, regardless of what anyone else does. For example, an audience member with Si = 2 will be seated at the beginning, but will stand up to clap later after she sees at least two other people standing and clapping.
If the shyness level of everyone in the audience is known, and additional friends of the singer can be invited to be in the audience, can it be ensured that everyone in the crowd stands up and claps in the end ? Each of these friends may have any shyness value. What is the minimum number of friends needed to be invited to guarantee a standing ovation?

int GetClappers(int N, List<int>S) 

{ 

int rem = 0; 

int cur = 0; 

for (int i = 0; i < N + 1; i++) 

{ 

   if ( i  > cur ) 

   { 

       rem += i - cur; 

       cur = i; 

   } 

   cur += S[i]; 

} 

return rem; 

}

We continue discussing the paper "Shielding applications from an untrusted cloud with Haven,” written by Andrew Baumann, Marcus Peinado, and Galen Hunt.  We discussed SGX optimizations that could be attempted in newer releases but were found in the study by the authors. We continue to review the SGX hardware notes in the paper. We were reviewing shielded VMs. Now we look at shielding without information leakage. The intermediate state of Haven is saved in encrypted form on disk so that the host does not know. But SGX shares information with the host such as exceptions and page faults. This becomes necessary for dynamic management of resources.Had they been static, the host need not observe guest states. Faulting addresses are important for the OS to use proper page replacement algorithm to manage physical memory. The OS multiplexes resources over varying demands from the application.
This can still work with shielded execution. Just the role of the resource manager needs to change. Presently the resource manager determines the quantity of resources such as the number of physical pages to allocate with the selection of specific resources namely the virtual to physical mapping. The authors say that if these were decoupled, it would give the host control only over resource quantities and allow the guest to choose specific resources to release when the allocations change. For example, memory would be managed by allocating physical pages in the host, but allow the guest to control its virtual mappings, and use self-paging to permit over-subscription. The host may ask a guest to release pages or release it all. The hardware could also support cache partitioning and discriminate the cache as similar to coloring or tagging the pages. This does not restrain physical allocations and the cache can be flushed and repartitioned. This therefore does not leak the guest state.
There are other kind of hardware that also support such security. Hardware security modules (HSM) are one such. They are used to protect high-value secrets such as keys in the cloud.  An HSM is a computing element that is tamperproof because it uses a physical barrier and a self destruct mechanism to erase data when the barrier is compromised. AWS offers this module and there are APIs for key manipulation, signing and encryption. As a result the cloud users keys are protected but other data must still be transiently decrypted in a general purpose node in order to use it. This reduces the attack surface but does not eliminate it when compared to storing data in the clear. Since it involves a dedicated hardware, HSMs are expensive.

We continue discussing the paper "Shielding applications from an untrusted cloud with Haven,” written by Andrew Baumann, Marcus Peinado, and Galen Hunt.  We discussed SGX optimizations that could be attempted in newer releases but were found in the study by the authors. We continue to review the SGX hardware notes in the paper. SGX is the first commodity hardware that permits efficient multiplexing among multiple isolated programs without relying on trusted software. But while SGX is isolating the virtual address space, it would be even more inclusive to isolate full virtual machines. There are several benefits to this. First the operating system will be included altogether and this expands the capabilities significantly. By supporting a complete guest operating system, we can have more than one processes in stead of isolating a portion of user address as we do today. Though this comes with a huge trade off of surface area increase for vulnerabilities but it is not the same as Type II hypervisors today because we are in fact encrypting and redefining the trusted computing base. The fundamental assumption that the host is untrusted can be expanded and used in different contexts which leads to more challenges to solve in building such hardware. For example, this involves multiple levels of address translation, privileged instructions and virtual devices. Since the assumption is the same, the architecture in the shield module would apply at this scope and level as well. Let us take the example of virtual or pseudo devices. Whether the device isolates itself depends on whether it is communicating across the interface we want to protect.Virtualization makes it easy to port because it is no longer bound to physical resources but even a virtual device needs to be shielded when it is communicating across the trust boundary. Virtual resources can enable multiplexing  over the same physical resources. It is not that all the devices need to be shielded so some can be grouped together for isolation. Encryption-decryption and the ability to resume from a saved state is key to implementing this solution. The design is based on the principle of policy/mechanism separation. The guest controls the policy for virtual resources while the host manages policy only for physical resources. Resources are different from devices we talked earlier. Virtual resources include such things as virtual address allocation, threads etc. Physical resources address such things as memory and CPU time. This design using policy/mechanism separation enables the host to merely allocate and bookkeep resources where as the shield manages the policies.  #codingexercise
We were discussing the Hamiltonian cycles in a complete graphy. The problem was stated this way.
In a complete undirected graph, there are n nodes numbered 1 to n and there are k forbidden edges. Find the number of Hamiltonian cycles in this graph that don't contain the forbidden edges. Assume that order of traversal does not matter.

We gave the solution as follows

Permutations of  nodes as represented by characters and their sequences as edges traversed. 
Void Permute (String a, StringBuilder b, bool[] used, List<string> edges) 
{ 
  If ( b.Length == a.Length)  { if ( edges.Any(x => b.contains(x)) == false) print b.ToString(); return;} 
  For (int I = 0; I < a.Length ; i++) 
  { 
    If (used[i]) continue; 
     used[i] = true; 
     B += A[i]; 
     Permute(a, b, used, edges);
     B [B.Length – 1] = ‘/0’; 
     used[i] = false; 
  } 
} 
One optimization we suggested was to bail early from a permutation when an edge already listed appears in the forbidden list.
Another way, we could optimize this is to generate all possible forbidden edge combinations using the given ones.
Then we list possible permutations of the Hamiltonian cycles. 
Finally we exclude the edges that contain any of the combinations.  
The key to improving performance this way is the patterns to match and cycles to run against. The latter is fixed in number but the former if comprehensive and attempted with longer patterns first, might be cheaper to execute. What we are trying to do is that if we sort the  pattern and the occurrences, we can do better than the naiive O(n^2) check

Paas, CloudFoundry and UI

User Interfaces and portals for Web applications have traditionally been deployed to dedicated virtual machines and are bound to it. When such applications need to be migrated, it involves manual intervention and planning. But both applications and services can both take benefits of CloudFoundry and PaaS. They are not restricted to the same physical machine that they were once deployed on. With these software, the applications and services can be rolled from one host to another seamlessly without any loss of functionality. They don't require any updates either to code or configuration when they are rolled between hosts.
User Interface is no exception. If APIs and services can avail the advantages of PaaS which include such things as automated code deployments from source control using say Jenkins, continuous monitoring of applications and services, consistent maintenance across applications and services, availability of multiple buildpacks and server software to host the applications. We will go through these benefits in detail shortly but let us take a look at the hosting requirements between API and UI in PaaS.
API software usually exposes an http/https endpoint and port for connectivity. While it may involve authentication, encryption and use of api-keys, all of these are done over basic authentication scheme or OAuth, they are  contained to api implementations and external service consolidators such as a gateway.  A user interface on the other hand may have to integrate with an identity provider and authentication mechanism such as SAML or OAuth external and probably central to an organization and not necessarily within the control of the applications and services framework. Fortunately these are facilitated with a route from the PaaS. The application merely has to handle the redirects from the said authentication mechanisms and the redirects are to specific name:port that can be ported between PaaS hosts as routes. The external ip address of the host and port can be retrieved in code as CF_INSTANCE_ADDR and CF_INSTANCE_PORT
Most of the UI code is generally written as static drop in /var/www folder or as a server side software such as node.js or django. In either case, the provisioning of UI could be attempted on CloudFoundry and PaaS by deploying the code and setting the environment variables such as HOME and WEBDIR

#codingexercise
Yesterday we discussed Hamiltonian cycles from complete graphs.
Permutations of  a string: 
Void Permute (String a, StringBuilder b, bool[] used, List<string> edges) 
{ 
  If ( b.Length == a.Length)  { if ( edges.Any(x => b.contains(x)) == false) print b.ToString(); return;} 
  For (int I = 0; I < a.Length ; i++) 
  { 
    If (used[i]) continue; 
     used[i] = true; 
     B += A[i]; 
     Permute(a, b, used, edges);
     B [B.Length – 1] = ‘/0’; 
     used[i] = false; 
  } 
}

Not the forbidden edges can actually be enumerated in different combinations and excluded from the permutations before a permutation reaches full length.