Today we continue to discuss the paper on 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 state. We saw how iFrames differ from boxes and why boxes are helpful with the Jigsaw design goals. A Jigsaw  application can have multiple boxes, but all of the boxes live in the same frame. Jigsaw code uses access modifiers to expose state to external domains. The Jigsaw runtime uses these modifiers to validate cross-domain operations. A single Jigsaw application may contain multiple  principals. Jigsaw places each of these principals in a separate box.  As with the DOM, a principal can access its parent principal object or the root.Principal objects can synchronize their writes to DOM storage. Each Jigsaw box can potentially contain a DOM tree and an associated visual field. The updates to these are constrained by the parent. A visual field consists of width height and location within the parents visual field and a z-order.  A parent can set these for the child. If a child wants to modify these, it can try but it has to be permitted by the parent. The child fires a  Jigsaw event on any modification and the parent must have a registered handler for the same. Visual fields can overlap but boxes cannot request overlapping  visual region. With the hierarchy, there  is fine control of the visual field and storage but a principal must still trust in its ancestors. DOM storage obstruction allows each origin to maintain a client-side key/value database. Jigsaw partitions this DOM storage.

#google codejam Riverflow problem:
A river receives water from tributaries that can be diverted to farms by farmers. Farmers choose an integer power of 2 from 1 to D both inclusive and toggle their usage everytime that many number of days has passed. Given N days history of water flow in the river, determine if the farmers are cheaters or the smallest number of farmers who could be diverting from the river.

int GetMinFarmers(int D, int N, List<int> flows)
{
bool cheaters = false;
int net = 0;
int farmers = 0;
for (int d = D; d >= 1; d /= 2)
{
    for (int i = 0; i < d; i++) {
         int net = flows[i+d]-flows[i] - flows[i+d-1] + flows[(i+2*d-1)%(2*d)];
                                                                 // i+d-1 stands for previous day to be reduced by next cycle
                                                                                          // (i+2*d-1)%(2*d) stands for the next cycle
         if (net%2) cheaters = true;
         net /= 2;
         if (net > 0){
                     farmers += net;
                     for(int j = i+d; j <= i+2*d;j++){
                           flows[j%(2*d)] -= net;
                     }
         }else{
                     farmers -= net;
                     for(int j = i; j <= i+d;j++){
                           flows[j%(2*d)] += net;
                     }
         }
    }
}
if (cheaters || flows[0] < 0)
   Console.WriteLine("cheaters");
return farmers;
}
#courtesy: Gnurdux

We discuss another code jam problem today

This one is about N-quails running away from a person where initially the person stands at the origin and the quails are on a straight line at some offset Pi from the origin. They are running  away from the person either to the left or to the right of the origin and continue to run in that direction with their respective constant speed Si. The speed of the man is Y another constant and he can change his direction at any time to collect all the quails.  How much time does it take at the minimum to collect all the quails.
For the quails moving in the same direction, he will have to catch up at the max of pi + Si × t. This will be the quail whose abs (pi ×si) weighting factor is greatest.  For the quails running in the other direction, he can finish running in one direction first and then switch to catching up on another side.  This will save him the trouble of covering already negotiated distances repeatedly. Consequently he must first pick the direction with the shorter weighting factor is greatest.
Assume si is all positive it's direction given by pi which is minus for left and plus for right
Int getMinTime (list <int> Pi, list <int> Si, int K)
{
Int min = 0; int leftmost=-1;
Int max = 0; int rightmost=Pi.count+1;
For ( int I = 0; I < Pi.Count; i++)
{
 If (Pi × Si < min) {min = Pi × Si;
 leftmost = i}
 If (Pi × Si > max) {max = Pi x Si;
rightmost=i;}
}
If (rightmost < pi.count +1 && K - S [rightmost] == 0) return -1;
If ( leftmost > -1 && K - S [leftmost] == 0) return -1;
Int t-right = 0;
Int t-left = 0;
If (rightmost < Pi.Count +1) t-right= P[rightmost]/ K - S [rightmost];
If (leftmost > -1) t-left = P [leftmost] / K  - S [leftmost];
Int total = 0;
If (abs(min) > abs (max))
{
// first right then left
total = t-left + 2 × t-right;
}
else
{
// first left then right
total = t-right + 2 x t-left;
}
return total;
}

Today we continue to discuss the paper on 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 state. We saw how iFrames differ from boxes and why boxes are helpful with the Jigsaw design goals.
First boxes have no way to communicate with each other even if they belong to the same origin. Only functions marked public on principal objects can make cross domain calls. Boxes define the set  of domains they interact with by exposing their principal objects
Second boxes can use hierarchical relationships to manage resources. The topmost box has full access as possible. The descendants are further narrowed in scope. The delegations are possible from parent to child but with increasing strictness.  The integrator can set acts that restrict access of a child to its local storage but cannot allow access to its own storage.
Third boxes allow synchronous calls with objects being passed by reference. This is a significant improvement over asynchronous calls with significant marshalling.

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 state. We saw some of the features and design goals of Jigsaw. We got familiar with some of the terms such as domain, principal and integrator. We also reviewed box which is an isolation container much like an iFrame for each principal  however there are three differences between a box and an iFrame . Two iFrames can directly access each other's Javascript's namespaces using frame references. But box explicitly prohibits this.  The only way to allow cross principal access is with access modifiers on the principal object. IFrames share same origin.
But boxes enable fault isolation and privilege separation from different principals that originate from the same domain
Another difference is that boxes use nesting relationships to secure the resoutces of the children. With this hierarchy, common object oriented practice of encapsulation and inheritance can be used to better facilitate the management of resources. The third difference between box and iFrame is their use of communication channels.  IFrames uses asynchronous  postmessage calls . These calls can only transmit immutables and not pass objects by reference. Boxes facilitate synchronous calls and don't require marshaling of objects with the use of proxy.
#coding exercise
Find least common multiple of two integers
Int lcm (int x, int y)
{
Return (x*y)/gcd (x,y);
}

#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

const int a[5][6]={1,1,4,1,1,10,2,2,2,6,2,2,1,1,7,1,1,19,1,1,7,9,1,19,2,2,14,10,2,92};

int GetMinArrangements(int R, int C)

{

assert(R > 0 && C> 0);

Int answer = 0;

For (int I = 1; I <= C; i++)

{

    Int d = gcd(C, i)

    answer += a[R-2][d-1];

}

return answer/C;

}

 

Int gcd(int x, int y)

{

If y == 0 return x;

return gcd(y, x % y);

}

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)