We continue discussing the paper "Shielding applications from an untrusted cloud with Haven,” written by Andrew Baumann, Marcus Peinado, and Galen Hunt. We saw that the cloud has a huge trusted computing base comprising of privilegd software, hypervisor, management tools, staff and law enforcement. Although there is a hierarchical security model, essentially any data can be observed and modified and even if encrypted on disk/net.  The current approaches in cloud computing include hardware security modules comprising of dedicated crypto hardware which is expensive, limited set of APIs that provide key storage and crypto operations. These are not general purpose and used only for sensitive data. From the hierarchical security model, the trusted hypervisors suffer the following problems : 1) System administrators have access to these 2) memory snooping and other physical attacks are possible and 3) the hypervisor can be tampered.
Some mitigation in this regard is to use trusted hardware such as a TPM chip where the Basic idea is that there is a signed measurement (hash) of privileged software, remote user checks measurement, and an incorrect attestation implies compromised software. However, the cloud provider merely applies patches and updates and must trust provider for current hash value.
Let us now look at Shielded execution: this is one which enables protection of  a specific program from the rest of the system say using sandboxing, doesn't require the program to be modified which is naiive to threats, ensures confidentiality and integrity of the program and its intermediate state, control flow etc such that input and output may be encrypted and lastly one where the host may deny service but cannot alter-behaviour.
The paper assumes a malicious cloud provider which is a convenient proxy for all real threats. This means all the providers software is malicious- hypervisor, firmware, management tools, etc. All hardware besides the cpu is untrusted - DMA attacks, DRAM snooping, cold boot etc. Denial of service and side channel attacks are out of scope because they can be mitigated with billing.
Intel SGX provides hardware isolation for what is called an enclave -  a trusted boundary.  These come with new instructions to establish, protect and gate must be called to enter. This processor supports remote attestation.Even the virtual address space has a earmarked enclave for code/data and page table mappings are checked to map only to an encrypted and integrity protected portion of physical memory. Registers are also protected and controls are transferred securely.
#codingexercise
You have a N*N matrix of 0 or 1. The 0 means cell is empty and 1 means cell is full. The matrix is such that the occupied cells have to be on top of each other from the bottom as if being acted upon by gravity. This matrix can be rotated clockwise by 90 degrees. And all the elements will then slide down by gravity. Perform the rotation and gravitation pull on the matrix

int[,] RotateAndDrop(int[, ] matrix, int N)
{
var newMatrix = new int[N,N];
for (int p = N-1; p >=0; p--)
  for (int q = 0; q <N; q++)
      newMatrix[q, N-p-1] = 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;
}

Today we discuss the paper "Shielding applications from an untrusted cloud with Haven,” written by Andrew Baumann, Marcus Peinado, and Galen Hunt. This paper focuses on a concept called "shielded execution", which protects the confidentiality and integrity of a program as well as the associated data from the platform on which it runs - the cloud operators operating system, administrative software and firmware.The researchers’ prototype, Haven, represents the first system that can achieve shielded execution of unmodified legacy applications on a commodity operating system and commodity hardware. The authors state that with Haven, applications can store data and perform computations with equivalent trust to local computing. This gives privacy from Cloud operator's provider staff and legal authorities.
In the old days, a database server would store the top secret data and the operating system would host the runtime both being protected by firewall but with these moving to the cloud, the data and the runtime can be compromised. Therefore applications running with sql or apache and with their bugs should be able to run privately in untrusted cloud on commodity hardware. The vulnerabilities with cloud are that there application, operating system, hypervisor, firmware/bootloader, management tools or people and Law enforcement are trusted in that order. This is a hierarchical security model and any data can be observed/modified even if encrypted on disk/net. Although the technique of protection involves older concepts such as sandboxing, the host is assumed to be malicious and with that said, the application program still doesn't require modification.
#interview question
There is a hat with W white balls and B black balls. Audience can draw two balls at a time and return one white ball if the colors are the same or return one black ball otherwise. In the end only one ball remains in the hat and we have to guess the color.
Answer Per the question, the audience is left with one black ball when she draws two blacks or she is left with a white ball. Similarly the hat loses a white ball when one  is returned or an unknown otherwise. The trick here is that each color has equal likelihood of leaving the hat so double the smaller number of W or B will be lost anyways. Then because the colors will remain the same only one of that color will remain. This works as long as W and B are not equal.

Today we revisit the number systems in octal and hexadecimal. The base for these number systems is 8 and 16 respectively. Therefore the distinct digit representations are that many in number. As the numbering continues beyond the base it wraps around to more number of digits. For example, 8 is 10 in Octal and 16 is 10 in hexadecimal. Similarly 31 is 1F and 32 is 20 in hexadecimal. As you can see each unit increment rolls a digit to the next one and carries over to the next place order in that system and this occurs after every length(base) numbers.
Therefore if we divide the number repeatedly by the base length and collect the remainders, we get the representation in that number system. This is what we implemented earlier. Now we look at sequential incrementing.

void GetSequence(String pattern, integer number)

{ 

char[] array = pattern.ToCharArray();

int baselen = array.Length;

String num = "0";

for (int i = 0; i < number; i++)

{

int len = num.Length;

if (num[len-1].ToIndex() + 1 >= baselen){

 bool carryover = true;

 int k = 1;

 if (len-k < 0) num.padleft();

 num[len-k] = array[num[len-k].ToIndex() + 1 % baselen];

 k = k + 1;

 while (carryover)

 {

    if (len-k < 0) num.padleft();

    if (num[len-k].ToIndex() + 1 >= baselen){

        carryover = true;

    }else{

        carryover = false;

    }

    num[len-k] = array[num[len-k].ToIndex() + 1 % baselen];

    k = k+1;

 }

}else{

num[len-1] = array[num[len-1].ToIndex() + 1 % baselen];

}

}

Console.WriteLine(num);

}

Today we look at a few summation formulas and properties.
Given a sequence a1, a2, ... of numbers, the finite sum a1 + a2 + ... +an where n is a positive number
This sum can be written as n(n+1)/2 when the terms are consecutive n numbers and its terms can be added in any order. This is called the arithmetic series and has an order of n^2. If the series is infinite and a limit exists then it is said to converge otherwise it is said to diverge. We can rearrange the terms of an absolutely convergent series.
For any real number c and any finite sequences a1, a2 ... am and b1, b2 ... bn
Sum  c.ak + bk where k can range from 1 to n is equivalent to writing
c.Sum ak + Sum bk and this is said to be the linearity property.
The linearity property is also obeyed by infinite convergent series.
Summation of squares and cubes also have well defined sums.
For example Sum of squares of consecutive 1 to n numbers is n(n+1)(2n+1)/6
and the sum of cubes of consecutive 1 to n numbers is n^2(n+1)^2 / 4
A series is said to be geometric or exponential when the terms are increasing in power such as 1 + x + x^2 + x^3 ... +x^n and x is not equal to  1.
The sum of this series has the value (x^(n+1)  - 1)/(x-1)
When the summation is infinite and the absolute value of x is less than 1, then we have the sum as 1 / (1-x)
A Harmonic series is one where the nth harmonic number is the sum of the consecutive fractions 1 + 1/2 + 1/3 + ... + 1/n which we calculate as ln n + a constant
Additional formulas can be obtained by integrating and differentiating the series above.
Telescopic series is one where for any sequence a0, a1, ..., an,
Sum for k = 1 to n (ak - ak-1) = an - a0
since each of the terms a1, a2, ..., an-1 is added in  exactly once and subtracted out exactly once. Hence the term telescopes.

#codingexericse 

Given a representation of all distinct digits in an alien system, Generate an increasing sequence from 1 to 9 

For example  given 01 and 0F8 as the alien number system 

0 = 0           0           F, 8, F0, FF, F8, 80, 8F, 88, F00, F0F 

1  = 1          F 

2  = 10        8 

3  = 11        F0 

4 = 100        FF 

5 = 101       F8 

6 =  110      80 

7  = 111      8F 

8 =  1000      88 

9 =  1001      F00 

10 = 1010    F0F 

                     F08 

                     FF0 

                     FFF 

                     FF8 

                     F80 

                     F8F 

                     F88 

                     888 

                   F000 

void GenSequence(String pattern, int number) 

{ 

char[] array = pattern.ToCharArray();  

int len = array.Length; 

String prefix = string.empty; 

while (number) 

{ 

   int rem = number%len; 

   prefix += array[rem]; 

   number = number / len; 

} 

Console.WriteLine(prefix.reverse()); 

}

Today we review the codejam question to determine the number of intersection point between lines connecting floors of two buildings.
In this case the connectors could connect floors at the same level or those above or those below on the opposite side. There is only one connector on each of the floors. The connectors intersect only when there is a  span across other connectors.
To determine the number of intersection points, we only need to look at the connectors that span others. This happens only in two cases - when the connectors connect floors above or when the connectors connect floors below. In each of those cases, if there are other connectors in their way, their endpoints would be within the range from the start to the end of the current connector. We can choose either the starting endpoints or the finishing endpoints and they could be different for the two cases. In both cases we will have to exclude one of the endpoints to determine the number of intersections. Intuitively, we are articulating that the intersections arise from connectors that lie within the start and the end of the chosen connector. If there are no intersections, the lines are parallel even if they are not horizontal and their start and end will not have the beginning or end of any other connectors within their start and end.

Now back to AWS Billing:
we were discussing how to archive the metrics

CREATE TABLE [dbo].[Metric]
(
[ID] INT NOT NULL PRIMARY KEY IDENTITY,
    [Label] NVARCHAR(50) NOT NULL DEFAULT 'UNKNOWN',
    [Created] DATETIME NOT NULL DEFAULT getdate(),
    [Value] REAL NOT NULL DEFAULT 0.00,
    [Type] NVARCHAR(50) NOT NULL DEFAULT 'Gauge',
    [Units] NVARCHAR(50) NOT NULL DEFAULT 'NA',
    [Service] NVARCHAR(50) NULL,
    [Region] NVARCHAR(50) NULL,
    [InstanceID] INT NULL,
    [ClusterID] INT NULL,
    [ProjectID] INT NULL,
    [Created By] NVARCHAR(50) NULL
)

GO

CREATE INDEX [IX_Metric_Created] ON [dbo].[Metric] ([Created])

GO

DECLARE @ID INT;
while EXISTS(SELECT * FROM Metric WHERE Created < '2014-01-01')
BEGIN
SELECT @ID=ID FROM Metric WHERE Created < '2014-01-01'
INSERT INTO Archive (Label, Created, Value, Type, Units, Service, Region, InstanceID, ClusterID, ProjectID, [Created By])
SELECT Label, Created, Value, Type, Units, Service, Region, InstanceID, ClusterID, ProjectID, [Created By] from Metric WHERE ID = @ID;
DELETE FROM Metric WHERE ID=@ID;
SELECT @ID=ID FROM Metric WHERE Created < '2014-01-01';
END

How do we calculate the CPU instance hours from AWS metrics?
Its true that AWS Metrics use the term CPUCredit which does not immediately tell us how many vcpu we are talking about. But this jargon is much more informational, true and accurate as we will see. In fact, they have a concept of CPUCreditUsage and CPUCreditBalance. So what is a CPU credit ? One CPU Credit is equal to one vCPU running at 100% utilization for one minute. Other combinations of vCPUs, utilization and time are also equal to one CPU credit for example one vCPU running at 50% utilization for two minutes etc. We can translate minutes to hours as well. In this case we can have 1/30 CPU credits for an hour which is equivalent to 1 CPU Credit
We say it is informational because it is not merely based on the static allocation of the number of cpus and instead based on the usage and balance of the utilization. This leads to the question how are CPU Credits earned ? Each instance for example a T2 instance  starts with a healthy initial CPU credit balance and then continuously receives a set rate of CPU credits per hour. This accounting is done at a millisecond level resolution and it ensures a maximum earned CPU credit balance for example 144 CPU credits  for a t2.micro. Thus these metrics are much more true and accurate. There are two metrics associated with CPU Credits - one is CPUCreditUsage and another is CPUCreditBalance. The CPUCreditUsage metric indicates the number of CPU credits used during the measurement period The CPUCreditBalance metric indicates the number of unused CPU Credits a T2 instance has earned. The CPUCreditUsage identifies the amount of time during which the physical CPUs were used for processing instructions by virtual CPUs allocated to the instance. Therefore this metric can directly be used to generate the bill. Moreover the CPU Utilization metric is aggregated for the number of cpus that instance may have. A t2.medium instance has two vCPUs and if one of them is at 100% and the other is rarely used, the CPU Utilization metric will show 50%.

Today we continue discussing the AWS Billing.
I referred to CloudWatch monitoring and SNS notifications as one way to populate a historical table of usage metrics. But there are some disadvantages to this
1) It requires elaborate setup and incurs further costs
2) As a cloud provider, this requires a lot of overhead for many hundreds of customers
3) Most of the usage is still under the free tier where the benefits are not that much.
On the other hand we can poll for the data that we are most interested in such as the number of instances and their image types. Furthermore, we can switch on CloudWatch for only those accounts where the usage is significantly higher than the free tier.
Therefore we wrote some sample scripts to illustrate :
1) how to get the instance information
2) how to poll for the information using cron jobs
3) how the datapoints from the usages look like
4) how to design a table to store such data
5) how to perform aggregation over this data

These scripts are shared at : https://github.com/ravibeta/PHPSamples

Note that both the poller and the SNS notifications are essentially providing data
1) for the meters that have been configured
2) the data can be accumulated for longer than the fourteen days max worth that the APIs provide
3) the datapoints for advanced metrics although come processed with filtering and aggregation at the source can be easily computed using other datapoints from essential metrics

Hence the use of a table helps with the history.
As with all historical tables, we may need to archive and trim it. This process can be done by moving one record at a time from the source table to the archive table The moving operation essentially identifies one of the records to be moved based on an archival policy (say older than a timeframe) and inserts into the archival table if it doesn't have it already, and then deletes from the source table when the insertion is successful.

#codejam
we now discuss another puzzle from the codejam which involves load testing.
The problem is described this way:
Let us say a site can support L people at a time without errors. but the site may have P visitors as the peak number of all visitors that the site may encounter.  Since the site cannot support that many visitors, the site has to determine within a factor of C, how many people it can support.  This means there is an integer a  such that you know the site can support a people, but you know the site can't support a * C people.
Note that this C is the target that we will use. This is given with each input of L and P. The goal is to determine the number of load tests you need to run in the worst case before knowing within a factor of C how many people the site can support.
Let us say this number is x.
The strategy we use is that if we know a then a*C is the maximum we can support, if P is greater than a*C we need to do more load tests for refining what a and a*C can be. Each refinement or iteration increments x by 1.
Logarithmic or exponential scaling may not always work. a 10x strategy might also not be sufficient. Depending on L and P and how large they can get we need to determine a suitable strategy.
Choosing the strategy depends on the range given by L and P. We want to scale L to P in the minimum number of steps. whichever strategy gives us this minimum number  of steps we take.
We essentially have two categories of problems which determine whether we need a strategy that takes big steps or small steps.
L and P are small
L and P are large.
We observe that since they are known along with C each load test can pick arbitrary number of machines to bound a and a*C, we can use the worst case always as the one where a*C fails the test.
if a*C passes the test then we can alternate with where a*C fails to find x - the number of iterations. The outcome of a load test is binary.

Now we take some examples to see how this works. We will directly use the examples given:
Input
  
Output
  
 total number of cases : 4
 L         P       C
 50    700       2      Case 1
 19      57       3      Case 2
 1    1000       2      Case 3
 24      97       2      Case 4

In case #2, we already know the site can support between 19 and 57 people. Since those are a factor of three apart we don't need to do any testing. Hence x is 0
In case #4, we can test 48 since it is a factor of 2 but in order to test 97 assuming 48 can be tested we will need another test and that will still be less than 97. The worst case is when 49 cannot be supported. 49 then to reliably say 97 can be supported we will need another test.
There is a lower bound and an upper bound of a window where we can say that a certain number (a) can be supported and a certain number (a*C) cannot be supported.

#context switch and revert back to aws billing
The CloudWatch monitoring subscriber can be hosted on an AWS machine because it will automatically provide dog fooding of the subscription. Let us say we host a web server that receives the JSON post callbacks from the subscriber. This subscriber can parse all the incoming messages to fill the metrics table while doing so increases the utilization of the instance which is also being watched, therefore adding validity to the machine. Furthermore, the web server is required to have a Internet addressable endpoint and this is facilitated by AWS instances.


 

yesterday we were discussing a problem where we had to find the number of passwords possible from observed M fingerprints and the password being N letters long.
We stated that when
M == N then the number of permutations is N!
If N > M then there are repetitions of some of the letters and we broke up the case as
               a letter appearing twice
               a letter appearing thrice
               :
               a letter appearing N-M+1 times
              and the above repeated for each of the M letters
The number of permutations in each case can be determined by dividing the permutations by the factorial of  the number of objects that are identical.
Let us take a few examples
For M=3 N=5 we have  M * (N!/(2!2!) + N!/3!)
For M=3 N=6 we have  M * (N!/(2!2!2!) +  N!/(3!2!1!) + N!/(4!1!1!)) where 4 = N-M+1
Note the denominators are such that the repetitions together with single occurrences add up to N
Finding the different denominators is easy because we are trying to find the sum s with at most p components where s = N and p = N-M
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace SumToN
{
    class Program
    {
        static void Main(string[] args)
        {
            var sequence = new List<int>();
            GenSeq(6, 3, ref sequence);
            PrintSequence(sequence);
        }
        static void PrintSequence(List<int> sequence)
        {
            Console.WriteLine();
            for(int i = 0; i < sequence.Count; i++) {Console.Write(sequence[i]);}
            Console.WriteLine();
            return;
        }
        static void GenSeq(int s, int p, ref List<int> sequence)
        {
            if (s == 0) {if(p==0)PrintSequence(sequence); return;}
            if (s != 0 && p == 0) { return; }
            for (int i = 0; i <= s; i++)
            {
                sequence.Add(i);
                GenSeq(s - i, p - 1, ref sequence);
                sequence.RemoveAt(sequence.Count - 1);
            }
        }
    }
}