#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.

Building a commercial Node.js user interface – some do’s and don’ts

If you want to develop Node.js applications coming from a PHP background, the following are some considerations as I have found them. For software developers who were writing user interface in languages such as PHP, writing model->view->controllers comes easy along with a host of useful widgets and controls. For example, Yii framework in PHP makes it elegant and performant to write such web applications. Common server side functionality includes connecting to a database and making API calls. Javascript validation is still used but the inline html execution along with the /var/www/ copy-deployment makes PHP different and easy for UI development.

With Node.js, the language is javascript and if we are familiar with the asynchronous programming model on the client side as is the case with client side scripts in PHP, then this is no different. The server side framework comes with rich templates and parsers such as Hogan/moustache and express for rendering the views. But here are some of the UI artifacts we would like to carry forward:

1)      Templates and variables as output from the controller to the view

we have fine control over the html we can send in the response. For example:

res.render('index', servers, function(err, html) {

             insertion = "<tr><td>{{ server.pk }}</td><td>{{ server.fields.server_id }}</td></tr>";
       var template = Hogan.compile(insertion);
       data = '';
       servers.forEach(function(server, index, array){
            var row = template.render({'server':server});
            data += row; 

             });
      var h = html.replace('LIST_OF_SERVERS', data);
      res.setHeader('Content-Type', 'text/html');
      res.send(h);
});

2)      Flash as a notification to the user for error and info

       req.flash('info', '%s items have been saved.', items.length);

3)      Session as a validation that the user is currently signed in

require('./saml/saml')(app);

function secure(req,res,next){

      // Check session

      if(req.session.currentUser){

        next();

      }else{

        app.settings.saml.startAuth(req, res);

      }

    }

app.all('/', secure); 

4)      Css and layouts as an organization and theme across views

<link rel="stylesheet" type="text/css" href="../stylesheets/screen.css" media="screen, projection" />

<script type="text/javascript" src="../javascripts/jquery.js"></script>

5)      Redirect and rendering  as appropriate

app.get('/', function (req, res){

  res.redirect(login_url);

});

6) Exception handling : Use appropriate state handlers such as the error: and success: in $.post calls and you should have less try-catch-finally to use

7) Logging: You can continue to use a logger that logs to a file

We continue discussing the paper "Shielding applications from an untrusted cloud with Haven,” written by Andrew Baumann, Marcus Peinado, and Galen Hunt. We were describing Haven and the limitations of the original Intel SGX.
It needed new instructions for dynamic memory allocation and protection. SGX doesn't report page faults or GPFs to the enclave and it permitted RDTSC and RDTSCP instructions for practicality and performance. The thread local storage can't reliably switch FS and GS. These were fixed in SGX v2. Haven was tested using SGX emulator. There was no direct SGX implementation at that time.
To overcome this for performance evaluation, a model was used. This model consisted of a TLB flush on Enclave crossings and a variable spin-delay for critical SGX instructions such as enclave crossings, dynamic memory allocation, protection, penalty for access to encrypted memory and slow overall system DRAM clock. The results showed that there was slowdown but it depended on model parameters. Apache had 35% slowdown, SQL Server had 65% slowdown as compared to VMs
10K plus cycles  for SGX instructions and 30% slower RAM was assumed for the study.
The application workloads were chosen as database and webserver to give two different perspectives.
The database server was Microsoft SQL Server 2014, Enterprise-edition and TPC-E, a standard online transaction processing benchmark. They use a default configuration for SQL Server when running naively or in a VM but for Drawbridge and Haven some parameters were varied. Drawbridge does not support large pages or locked physical allocations so they were disabled. The buffer cache was limited to 6.5 GB because LibOS does not report physical memory usage and the server's default behaviour led to excessive paging. The TPC-E clients ran on a single machine connected to a test system by a local gigabit network.For each run, 30 minutes of warm up time were allowed and then the transaction performance was measured for an hour. The web server was Apache 2.4.7. and PHP 5.5.11. The Drawbridge was configured to run Apache's worker processes in the same address space and enclave and modified Apache's configuration to avoid using AcceptEx, which exposed a compatibility bug in LibOS socket code. Mediawiki was backed by a SQLLite database and enabled the alternative PHP Cache for intermediate code and MediaWiki page data. The server was benchmarked using 50 worker threads on the client that repeatedly fetched 14kB main page over persistent SSL connections for a period of 5 minutes.
#codingquestion
Given a set of M unix paths that already exist and N paths that need to be created, find out how many mkdir commands without options need to be given
int GetNumMkdirs(SortedList<string> created, SortedList<string>todo)
{
int count = 0;
foreach (var item in todo)
{
var parts = item.split('/');
string sep ="/";
for (int I = parts.count; I > 0; I--)
{
    result = "/" + String.Join(sep, val, 0, i);
    if (created.contains(result)){
        break;
    }
    count += 1;
}
for (int I = 0; I < parts.count+1; I++)
{
   result = "/" + String.Join(sep, val, 0, i);
   if (created.contains(result) == false)
       created.Add(result);
}
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 describing the shield module uses a reserved area of protected memory and file system and does a sanity check of untrusted inputs. The host may deny service but it cannot alter the behavior of the application. The host maybe malicious for example it may support lago attack. A lago attack is one where the host fails system calls to gain access to the users stack. More on this to come later. To mitigate the lago attacks a shield module includes typical kernel functionality such as scheduling, VM, file system, and interacts with the untrusted interface with host. The shield module has a memory allocator for which the host commits or protects specific pages and performs no address allocation. A private file system is provided by the host. The shield module has a scheduler that does not trust host to schedule threads. It has an exception handler that emulates some instructions. It performs sanity check of untested inputs.

The other kinds of attacks are where the application itself cannot be trusted and the operating system cannot be trusted. That is why the enclave protects guest from the host while the picoprocess it is running in protects host from the guest. The enclave loads the unmodified binaries of the application, a module that forms a subset of windows to run in process and the shield module. The module that interacts with the application binaries uses the windows API and with the shield module using the Drawbridge ABI. The windows kernel loads the Drawbridge host and SGX driver. This enclave is Haven.
The original intel SGX had its limitations. It needed new instructions for dynamic memory allocation and protection. SGX doesn't report page faults or GPFs to the enclave and it permitted RDTSC and RDTSCP instructions for practicality and performance. The thread local storage can't reliably switch FS and GS. These were fixed in SGX v2.
#codingquestion
To the problem described in the previous post, if two players playing red and blue occupy the positions marked 1 alternative determine who will have four pieces in a row when you rotate the board.
Modify BoardHasFourInRow to take color as a parameter and add the check matrix[i,j] == color in as the first condition to proceed or exit in FourInRow function.
void PrintWinner(int[,] matrix, int N)
{
RotateAndDrop(matrix, N);
bool blue = BoardHasFourInRow(matrix, N, BLUE);
bool red = BoardHasFourInRow(matrix, N, RED);
if (blue && red) { Console.Write("both"); return;}
if (blue) { Console.Write("blue"); return;}
if (red) { Console.Write("red"); return;}
Console.Write("neither");
}
int GetMax(List<int> numbers)
{
return numbers.Max();
}
int GetMin(List<int> numbers)
{
return numbers.Min();
}

We continue discussing the paper "Shielding applications from an untrusted cloud with Haven,” written by Andrew Baumann, Marcus Peinado, and Galen Hunt. We were describing how the paper assumes a malicious cloud provider which is a convenient proxy for all real threats. And how it utilizes the hardware isolation provided by Intel SGX to form an enclave and utilizes attestation. This hardware isolation involved new instructions to establish, protect and a gate to be called to enter.A portion of physical memory was encrypted and integrity protected. We now cite some of the attack vectors that influenced the design. The first is lago attacks. This is one where a malicious kernel with a carefully chosen sequence of integer return values to system calls  can lead a supposedly protected process to act against its interest. For example, malloc() returns pointers to user's stack and read() fails with EROFs in a competing system. This paper suggest not to check all the system calls but to admit  OS into the trusted computing base and using a drawbridge ABI ( a selection of few runtime calls) for a shield module within the enclave to communicate with the runtime. The untrusted interface is between the shield module and the untrusted runtime and there is a policy mechanism  enforced by approximately twenty calls with restricted semantics. The policy in the guest is a virtual resource policy affecting virtual address allocation and threads while the policy in the host is a physical resource policy affecting physical pages, VCPUs. The shield module uses a reserved area of protected memory and file system and does a sanity check of untrusted inputs
#codingexercise
To the exercise described earlier using an N*N matrix of 0 and 1, perform an anticlockwise  rotation and gravitation pull on the matrix.

Start      Rotate         Pull

0000      0000          0000

0000      0011          0001

0110      0011          0011

1110      0001          0011
int[,] RotateAndDrop(int[, ] matrix, int N)
{
var newMatrix = new int[N,N];
for (int p = N-1; p >=0; p--)
  for (int  q= N-1; q >= 0; q--)
      newMatrix[N-q-1, p] = Matrix[p,q];
for (int j = 0; j < N; j++)
  for (int i = N-1; i >= 0; i--)
      if (newMatrix[i,j] == 0 && i-1 >=0){
newMatrix[i,j] = newMatrix[i-1,j];
newMatrix [i-1,j] =0;
}
return newMatrix;
}

Check whether the final position  of the board has four elements in a row either horizontally, vertically or diagonally
bool BoardHasFourInRow(int[,] matrix, int N)
{
for (int i =0; i<N; i++)
  for (int j = 0; j<N; j++)
     if (FourInRow(matrix, N, i,j) == true) return true;
return false;
}

Bool FourInRow( int [,] matrix, int N, int i, intj)
{

// horizontal count
Int h = 0;
Int x = i;
While (x>0 && matrix [x,j] == matrix[i,j]) {h++;x--;}
x = i+1;
While (x < N && matrix [x, j] == matrix [i, j]) {h++; x++;}
If h >=4 return true;

//vertical count
Int v = 0;
Int y = j;
While (y>0 && matrix [i,y] == matrix[i,j]) {v++;y--;}
y= j+1;
While (y < N && matrix [i, y] == matrix [i, j]) {v++; y++;}
If v>=4 return true;

// diagonal forward
int d = 0;
x = i;
y = j;
While (x> 0 && y>0 && matrix [x,y] == matrix[i,j]) {d++;y--;x--;}
y= j+1;x=i+1;
While (x < N  && y < N && matrix [x, y] == matrix [i, j]) {d++; y++;x++;}
If d>=4 return true;

// diagonal backward

d=0;

x=i;

y=j;

While (x> 0 && y<N && matrix [x,y] == matrix[i,j]) {d++;y++;x--;}
y= j-1;x=i+1;
While (x < N  && y > 0 && matrix [x, y] == matrix [i, j]) {d++; y--;x++;}
If d>=4 return true;

return false;
}