Today we continue reading Jigsaw : Efficient, low effort mashup isolation by James Mickens and Matthew Finifter. Mashups are web applications that contain code from different principals.
Jigsaw lets mashups be isolated with its framework  and lets them selectively expose private states. Jigsaw had four goals:
Isolation by default: The integrator has access to browser resources and the guest may be provided some access. However by default a guest cannot access these resources. Most principal's JavaScript namespace is hidden from external code by default .
Efficient, synchronous sharing: Jigsaw enables synchronous, pass-by-reference sharing. If an object is to be shared outside its local domain, a proxy or 'surrogate' automatically wraps and unwraps the object.
Simplicity: Using the above two, Jigsaw can secure mashups with a few lines of policy code
Fail-safe legacy code: If legacy code has not been adapted for Jigsaw, it will work within a single domain and unmodified legacy code will fail safely when accessed by external domains.

Jigsaw prohibits  some Javascript features but these are advanced features that are typically not used and usually exploited by malicious programs. Jigsaw also makes some changes to the core JavaScript language  only to make it behave more like an object oriented. Jigsaw also preserves many of the language features that make JavaScript an easy to use scripting language. For example, objects are passed by reference even when they are exposed out of the isolation domain.
Jigsaw does mashups from different domains. Domains are origins just as we use it in the term cross origin policy. A principal is an instance of web-content provided by a particular domain. An integrator is one that includes another principal by explicitly downloading content from the other principal's origin. Principals can be chained and consolidated just like in a tree hierarchy. A user visiting a top level site is visiting an integrator.
Jigsaw also has a concept of a box. Each box is associated with the following resources:
a JavaScript namespace containing application defined objects and functions
a DOM tree which represents the HTML or CSS of the principal
an event loop which captures mouse and keyboard activity intended for that box
a rectangular visual region with a width, height and location within the larger browser viewport
a network connection which allows the principal to issue HTTP fetches and data.
a local storage area which stores cookie and implements the DOM storage abstraction.
#codejam problem
A R x C matrix of positive numbers wraps around a drum. Each number represents the number of cells that share an edge with the cell of the same number. For eg the front and back of the drum can be :
3  3  3
3  3  3
2  2  2
The top and bottom of the drum can be different so the line containing 2 can appear in the first line instead of the last and this will make it a different arrangement. If an arrangement can be rotated to get another, they are the same. How many different arrangements exist for given R x C
Solution:
htamas gave a python solution as follows:
Take an inital pattern with the positive integer 1 and take initial patterns of these numbers for arrays of 1 x 5 When arranged vertically we can take the arrays corresponding to rows a1, a3, a4, a6, a12. For all rows greater than five  to R + 1, we can repeat their sequences as a pattern of the previous. That is a3 can be extended based on a sequence of a3 and a1 and so on.
The initial answer will be sum of the R and R - 2 column in a.
If the column C is divisible by 3, 4, 6 and 12, the corresponding columns from the a3, a4, a6 and a12 will cumulate to the answer and when we take a modulo with a sufficiently large number we can be accurate to that extent.

Today we continue reading Jigsaw : Efficient, low effort mashup isolation by James Mickens and Matthew Finifter. Mashups are web applications that contain code from different principals.  These principals often have a lop sided trust relationships with each other. For example, a page that shows local news may receive data from a news feed component  and a  map component.  The integrating page may want to isolate both components from each other and present them with an extremely narrow interface to the integrators state. We read that Jigsaw is a framework that extends Javascript and facilitates securing the data sources with simple keywords like public and private.
There have been previous approaches as well but the frameworks were overly complex and presented an unwieldy tool. Many of these approaches force developers to use asynchronous, pass-by value channels for cross principal communication channel.The difficulty with pass-by-value asynchronous calls besides introducing subtle data races is that it introduces high serialization overheads Previous work that involves object views were too general often requiring policy code for each property access on a shared object. The same goes for ConScript policy files where the policy consists of arbitrary Javascript code. They are not only expensive, unnecessary but also too cumbersome for large graphs of objects. The mashups only need to be secured with a yes-no mechanism to define whether they are externally shareable and a simple grammar that restricts access to persistent storage and visual display. These two policy primitives are sufficient for mashups. Consequently they require only simple constructs.
Jigsaw does this and better. It not only lets mashups be isolated with its framework but also it lets them selectively expose private state with the following four goals:
Isolation by default: The integrator has access to browser resources and the guest may be provided some access. However by default a guest cannot access these resources. Most principal's JavaScript namespace is hidden from external code by default .
Efficient, synchronous sharing: Jigsaw enables synchronous, pass-by-reference sharing. If an object is to be shared outside its local domain, a proxy or 'surrogate' automatically wraps and unwraps the object.
Simplicity: Using the above two, Jigsaw can secure mashups with a few lines of policy code
Fail-safe legacy code: If legacy code has not been adapted for Jigsaw, it will work within a single domain and unmodified legacy code will fail safely when accessed by external domains.
#codejam problem
Why does two datapoints suffice in the deer hike problem we saw earlier
Because there are limited number of positions that can be taken on the trail. For example there are 0 to 360 both ends included and a single hiker can occupy all these positions at some point of time. Therefore we are only looking for a safe spot between two hikers which can give an intermediate position for the deer. Since one position is enough, either that position will have encounter or not. Therefore we get our answer.

Today we read a different paper.  This one is titled Jigsaw : Efficient, low effort mashup isolation by James Mickens and Matthew Finifter. Mashups are web applications that contain code from different principals.  These principals often have a lop sided trust relationships with each other. For example, a page that shows local news may receive data from a news feed component  and a  map component.  The integrating page may want to isolate both components from each other and present them with an extremely narrow interface to the integrators state. Another example might be where a social networking page might embed a third party application and an advertisement.  As we can see this applies to web application rendering content from different microservices.  Securing such a mashup application is challenging because the source of the data may not want to expose anything more than a narrow interface to their private code and data. Jigsaw is a new framework that isolates these mashup components.It is an extension of Javascript language and requires a Jigsaw to Javascript compiler. Jigsaw differs from its predecessors in the simplicity of its syntax to make it easy for a domain to tag internal data as externally visible. It uses the well-understood public / private keywords which developers are familiar with. Also unlike previous approaches, it allows mutually distrusting code to runs inside the same frame, this allows scripts to share state using synchronous method calls instead of asynchronous message passing. Yet it provides strong iframe like isolation, Since the code runs within the iframe, Jigsaw allows code to share state using synchronous method calls instead of asynchronous message passing. Also Jigsaw introduces a new encapsulation mechanism called surrogates. Surrogates allow domains to safely exchange objects by reference instead of by value. This improves sharing efficiency by eliminating cross-origin marshaling overhead.  A developers primary challenge in creating mashups is the wide range of trust relationships between mashups.  Sharing information between principals is desired but often required in explicit and controlled ways. This framework makes alleviates this onus and makes it easier for the developers. By implementing it in Javascript, the framework is available to include as client side scripts. This framework also improves the language' support for encapsulation.

#codejam problem

There are N hot water  taps that can be opened and closed one at a time to fill a reservoir with volume V and temperature T. Each tap has a rate Ri and temperature Ti. Find the minimum time required to fill the reservoir. 

If N == 1,
       if T != T0 return -1;
       return time-taken  = v/R0
If N > 1
     If T < min (T0, T1) or T > max ( T0, T1)
              Return -1;
     If T0 == T1 return time taken = v/ (R0+R1)

        t0 = (V - V * T / T1) / (R0 - R0 * T0 / T1)

        t1 = (V * T - t0 * R0 * T0) / (R1 * T1)
      #The respective contributions are taken into account above and since they are independent they can be opened simultaneously
       Return max (t0, t1);
       Courtesy: Zibada Similar to the deer hike problem mentioned earlier

#codingexercise
For simultaneous flow from more than two taps above, we would have the forms
(V - V×T/T1 -V× T/ T2)/ (R0- R0*T0/T1 - R0*T0/T2)

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. We also looked at hybrid applications that also used encryption. When compared to these systems, Haven seems the first to implement shielded execution of unmodified server applications in an untrusted cloud host. This is roughly equivalent to a user operating their own hardware in a locked cage at a collocation facility.  The host only provides raw resources such as  processor cycles, storage and networking. It can deny service but cannot but cannot observe or modify user data except those in transit and this is called shielded execution. A shielded execution fundamentally guarantees confidentiality and integrity. The former implies that the execution of the shielded program appears as a "black box" to the rest of the system. The latter implies that the system cannot affect the behaviour of the program.  Haven leverages Intel SGX which allows a process to instantiate a secure region of address space known as an enclave. Then execution of code within this enclave is then protected. While the code assumes the OS would behave correctly, the host OS may be malicious. Therefore Haven implements a protected runtime using an in-enclave Library OS (LibOS) using a mutually distrusting interface with the host OS. Combined with a remote attestation mechanism, Haven gives the user end to end guarantee of application security without distrusting the cloud provider, it software or hardware beyond the processor itself. The studies in this paper furthered improvements to SGX to enable efficient shielded execution. SGX performs memory protection by mediating page mappings at enclave setup and maintains shadow state for each page. These pages are allocated by the OS but must occupy a specific region of the physical memory. SGX supports CPU based attestation enabling a remote system to verify cryptographically that specific software has been loaded within an enclave, and establish shared secrets allowing it to bootstrap an end to end encrypted channel within the enclave. SGX also mediates transitions into and out of the enclave and protects the enclave's register file from the OS exception handlers. Revised SGX includes new instructions that allow the enclave and the host OS to co-operatively add/remove pages and modify their permissions. In addion to leveraging SGX, Haven builds on Drawbridge that supports low overhead sandboxing of Windows applications. Thus Haven's design is based on a shield module, an untrusted interface and an untrusted runtime.
#codejam problem
A country has D denominations of its currency.  A new rule mandates that only C number of any denomination may be used. How many minimum new dominations must the mint owner issue to enable all sums from 1 to  a given value V?
int GetMinNewValues(List<int>N, int D, int C, int V)
{
Assert  (N.count == D);
int r = 0;
int m = 1;
while (m <= V)
{
   if  (N.Count > 0 and N[0] <= m)
   {
         m += N[0] * C;
         N.RemoveAt(0);
    }
    else
    {
            r  += 1;
            m += m * C;
     }
}
return r;
}
http://1drv.ms/1RcXlib

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;
}