We continue with the list of important software incidents in recent history as described here. 
30) mistaken blame - Sometimes incidents are attributed to software bugs when in fact they occur due to manual error.Notably, a self-driven car covered 2994 miles coast to coast with three passengers in about 57 hours. While it did this successfully there were a few moments when the car was negotiating turns at high speed and instead of following the apex, it was trying to follow the lanes. The car could have careened off but it was held stable by hands on the wheels This is not a software bug but the system was being made to operate outside the zone of recommended speed. The accomplishments far outweigh the blame.  There are in fact far fewer if any accidents involving normal use of self-driven cars.  That said several accidents are avoided due to the practice of disengagement where a human safety driver takes control of the wheels. Every maker of self-driven car has to report the number of disengagements to give an indication of the overall safety. Google for instance reported 341 disengagements in 424000 autonomous miles over a period of fourteen months in 49 self driving cars.
31) trust the trusted - Some instruments are used for the comfort of knowing they represent security. Private keys are used as such for purposes of encrypting data either at rest or in transit. These keys are cut with random numbers but in some cases the random numbers could be predictable throwing open the possibility of keys being compromised.  This was the case with Valgrind which is a maintainer of Debian. In a software patch of the OpenSSL, the random number generator was broken. The patch was uploaded in late 2006 and made its way into the official release and only reported in early 2008. Keys that were cut with the patch were all compromised in that sense and so was anything that they protected. Still keys continue to be used for encryption.
32) Tunnels - Most people are familiar with the use of https and vpn as securing point to point traffic while absence allows traffic to be visible and even routed in the open. They assume an encrypted channel to be one continuous tunnel for the application. But a proxy can exist breaking the tunnel into two and pretending to be the receiver for the sender and the sender for the receiver at the same time.  
#codingexercise
find the count of appearances of a given digit k insequential numbers upto n
int GetCount(int n,  int k)
{
int count = 0;
for (int i = 0; i <=n; i++)
{
var digits = i.ToDigits();
count += digits.Count(t => t == k);
}
return count;
}
Each digit may appear in combinations of lengths 1 to len(ToDigits(n)) and this can be counted in the form of binomial coefficients. Moreover the digit can occur in repetitions for the same length it can only be repeated for the length of the combination again countable by the binomial coefficients. Each repetition can also have permutations This can help avoiding sequential check for the numbers upto a watermark smaller than the number.

We continue with the list of important software incidents in recent history as described here. 

28) When the fix is worse - Digital content manufacturers take great precautions to thwart software piracy. In one case they even overreached and did more harm than what the buyer had paid for. Sony BMG produced a Van Zant music CD that employed a copy protection mechanism that was scandalous. It involved installing programs that modifies the operating systems to interfere with the CD copying.  It also installed another program that would "dial home" the listening habits of the CD buyer. Both programs were not informed to the user. Further they both made the users' computer vulnerable to Trojan horse attacks. Other malicious programs could take advantage of the newly created vulnerabilities and escalate the threats against the target computer. Neither program could easily be uninstalled.  The user who bought the CD to listen to music may even risk compromising the computer. The programs that came with the CD also installed open source libraries which itself was a copyright infringement. Moreover, they were not up-to-date and had severe security vulnerabilities. Programs like these that the users did not ask for but are potentially dangerous are termed rootkits. Sony initially denied that these rootkits were harmful. Subsequently it tried to un-hide the programs, provided a so called uninstaller that ended up installing more unwanted software and introducing more security vulnerabilities. These new patches were also difficult to uninstall. To make things worse, the uninstalled collected the email address of the buyer.  Sony tried to do a recall but only ten percent of the CDs met that. But it did suspend the copy protection mechanism altogether in 2007. There was a lot of public outcry, government investigations and class action lawsuits. Sony tried to settle all these. Eventually a new and improved software removal tool was provided. It might be interesting to note that the Winternals tool maker actually found the issue on his computer and when Sony made the first round of uninstaller, he was also the first to say that the installer was worse in terms of leaving the computer more vulnerable. Winternals toolsets are popular utilites to work with different aspects of the operating system for routine, troubleshooting and additional tasks.

29) Shell scripting - Perhaps the most illustrative impact of improper shell scripting could be seen with the case of Valve's steam client for Linux. This had an unsafe shell script that did not check whether some of the cleanup steps were appropriate. In particular, if a user moved the installation director, it would summarily delete every file from every folder that the user had. The shell scripts would use the value of a global variable  and unconditionally delete every file and folder from the location pointed by the value.  The author of the script actually had a comment over the instruction that read "Scary!" and yet the shell script was made available to users.  Data corruption is itself bad but data loss without possibility for restore is unpardonable for many users especially when the fix was simply to tighten the script.
#codingexercise
find the count of appearances of a given digit k in a list of numbers A
int GetCount(List<int> A, int k)
{
int count = 0;
A.ForEach(x=>{
var digits = x.ToDigits();
count += digits.Count(t => t == k);
});
return count;
}

We continue with the list of important software incidents in recent history as described here. 
25) Pirates - On August 24, 2007 Microsoft Windows Genuine Advantage servers suffered an outage. Users who had legitimate copies of Windows XP and Vista were told they had counterfeit. The issue was resolved twelve hours later but not until around 12000 systems were affected worldwide. The bug occurred because a beta software was installed on the WGA servers which affected both activations and validations. The validation service was affected even after the rollback took place. The beta software had not kept pace with the encryption and decryption of product keys out in the field. Consequently, the requests for activation and validation were declined. Its interesting to note that this incident was not the same as an outage. If the WGA servers were offline or the services had become unavailable, customer copies of Windows would have defaulted to genuine. However the Beta software was unable to interpret the product keys and gave an incorrect response. While this impacted activation failures, the validation services were impacted longer even after the beta sofware was rolled back.
26)  When the data is large - Often bugs manifest because there is a lot of manual steps. Take the case of Apple maps in 2012. It was brought in as a replacement for Google Maps. Creating such maps take a lot of work in integrating from different sources often requiring manual supervision and handling. Google had several years to do that while Apple didn't. This led to lakes, train stations, bridges and tourist attractions going missing or mislabeled.  The Washington Monument moved across the street. Riverside Hospital appeared in Jacksonville, Florida while it had ceased to exist several years back. Auckland's main train station was in the middle of the ocean.  Similar issues have surfaced with other map makers as well because the work is inherently tiresome and error prone. Some have even claimed that it is not just data but also operations associated that result in error such as zooming in and zooming out of the maps.
27) Units - Its not just data and operations that need to jive. Software must also comply with standards between companies. Take for instance the failure of Mars Climate Orbiter in 1998.  This was about a 655 million space probe that disintegrated in Martian atmosphere because it was thrusted at a wrong angle It turned out that the thruster's output was calculated by a ground based computer software in non-SI units of pound-seconds instead of the SI-units of newton-seconds that was specified in the contract between NASA and Lockheed. The spacecraft encountered Mars on a trajectory that brought it too close to the planet. #codingexercise
Find the diameter of a binary tree
int diameter (node root )
{
If (root == null) return 0;
Int lh = height(root. Left);
Int rh = height(root.right);
Int ld = diameter (root.left);
Int rd = diameter (root.right);
Return max (lh + rh +1, ld, rd);
}

We continue with the list of important software incidents in recent history as described here.   
22) At the heart - X-Ray was not the only place where a software bug could do damage. Heart devices were also found possible to be hacked.  Organ transplants implied replacing body parts with new. But these need not just be donor supplied biological alternatives but artificial ones as well. With the artificial ones needing to be maintained, patients needed trips to the doctor's office. Instead some of these devices made it possible to be controlled automatically or even in some cases remotely over the internet. This helps patient monitoring but there was not much attention paid to the security of medical devices which leads it vulnerable to hacking.
23) Power out - In 2003, there was a widespread power outage that occurred throughout the  parts of the Northeastern and Midwestern United States. It was the most widespread blackout in history.  It was triggered by a software bug in the alarm system which failed to sound after overloaded transmission lines hit obstruction. If the alarm had sounded, it would have been easier to redistribute power. The bug was a race condition in GE's XA/21 monitoring software.
24) messaging - Network nodes often exchange messages indicating the health of the peer and the actions to be taken. In 1990, AT&T long distance network crashed when the failure of one switching system would cause a message to be sent to nearby switching units. This message however made the recipient fail as well resulting in a wave of failures that swept the network. Such failures are often termed cascading failure.

#codingexercise
Find the count of numbers that begin and end with the same digit in a given range of sequential positive integers. 
Int GetCount(List<int> numbers) 
{ 
Int count = 0; 
for (int I = 0; I  numbers.Count; I++) 
{ 
Var digits = numbers[I].ToDigits(); 
If (digits.first() == digits.last()) 
     Count++; 
} 
Return count; 
}

This is a continuation of the list of important software incidents in recent history as described here.   

17) Ping of death - Perhaps the ubiquity of computers and their networking protocols make it vulnerable to the attacks over the wire. In 1995/1996 the networking stack on the computers was not as hardened as they are today. Packet fragmentation and reassembly code were missing checks and error handling at the protocol level. In this case, a malformed ping packet could lead to a crash of the operating system. The Windows operating system showed a blue screen when they received these packets but the attacks and failures were not limited to Windows and affected other operating systems too. 

18) Stack of vulnerabilties - Since the networking stack other than TCP/IP such as the tunneling protocols were also not hardened prior to 2002, they were also vulnerable to malformed packets causing system crash. A variety of protcols were exploited but perhaps the point to point tunneling protocol manifested the most number of such vulnerabilities.  The size and format of the packets, the validity of the fields, the exchange sequence, the states of the state machine implemented by the protocols, the position on the stack for the protocol, the authentication and encryption mechanisms etc were all subsequently analyzed in a major security improvement. Today encryption and private key based authentication is widely used everywhere.
19) Random numbers - Many protocols and mechanisms rely on random number generation. However, the numbers generated can be random only when they are seeded properly. Even the authors of Kerberos  failed to safeguard against this bug. It was therefore possible to break into any computer that relies on Kerberos for authentication. However these vulnerabilities were not significantly exploited. Moreover, Kerberos had an elegant protocol design and the code was widely available making it hugely popular. 
20) Number crunching - In terms of public relations nightmare, perhaps the Intel Pentium floating point divide error stands out. The chip maker made mistakes when dividing floating point numbers that occur within a certain range. For example, dividing 4195835 by 3145727 resulted in 1.33374 instead of 1.33382 which was an error margin of over 6 percent. In scientific computing, this kind of mistakes may alter analysis and worse yet may even go unnoticed. Although, it was not clear how many users were affected, the company eventually agreed to replace each and every unit. This bug was over 475 million dollars in cost.

21) X-Ray - Perhaps the most well known of all bugs in the medical industry was the bug in the code controlling the Therac-25 radiation therapy which was responsible for at least five patient deaths in 1980 The defect was that a one byte counter in a testing routine frequently overflowed. when an operator provided the manual input to the machine at the time of an overflow, an interlock would fail. This interlock was the one that helped spread the electron beam by rotating a spreader plate. In its absence a lethal dose of radiation would hit the patient who described it as an intense electric shock. This would result in radiation burns, radiation poisoning and eventual death of the patient.

Courtesy: Internet sources, personal experience, Wired magazine, Bell Laboratories paper
#codingexercise
Yesterday we were describing how to find the length of the largest region in a boolean matrix. A region is a group of cells with value 1 such that each cell is adjacent to another cell also with value 1 and adjacency can be horizontal, vertical or diagonal.
The DFS is implemented here:
void DFS(int[,] A, int row, int col, int row, int col, ref int[,] visited, ref int  size)
{

var rd = { -1,-1,-1,0,0,1,1, 1};
var cd = { -1,0,1,-1,0,1,-1,0,1 };

visited[row,col] = true;
for (int k = 0; k < 8; k++)
    if (isSafe(A, row,col, row + rd[k], col +cd[k])){
           size++;
           DFS(A, row,col, row+rd[k], col+cd[k], ref visited, ref size);
}

}
DFS attempts all the eight adjacent cells a d only proceeds to recursion on that when it is safe to do that. Here safe means the cell is a valid position, has a 1 and has not been visited before. All the eight adjacent positions are tried.

This is a continuation of the list of important software incidents in recent history as described here.   

11) Price markdown: A wrong position of a decimal in the price of an item can make it very popular for purchase and often resulting in tremendous loss for the online retailer. This was exactly the case in its sale of first class air tickets on Feb 11 2015 on its Danish website by United Airlines. The flight from London to New York was priced $74 which was a discount of over 5000 US dollars.  The glitch was unnoticed for several hours and as per the quotes, resulted in “several thousand” tickets purchase attempts. Fortunately some of the safeguards within the website’s purchasing deterred many buyers. 

12) Price Markup: The price of the item need not come down for buyers to take advantage of the company. Mr.Klug from San Mateo California bought Discovery Channel CDs from Amazon for a ticker price of $2,904,980,000 plus shipping and handling. Since he had an Amazon Visa three percent rewards card, he was entitled to roughly $87 million in rewards. Thankfully for Mr.Klug, his card was not charged by Amazon because as per their policy they don’t charge until the item is in packaging.  

13) Price wars: It’s one thing for a company to make mistakes on the price of its products. It’s another for companies to compete with each other for the lowest price in favor of the buyer. This was the case again with Amazon. Discounts were offered on Apple MacBook in November 2016 but the discount was calculated wrong and resulted in over 360$ off the regular price far lower than any competitor. Although the misprice was found and rectified, within a few hours, it didn’t stop buyers from making good on the price and the company decided to honor them anyways.  

14) Space age: Software bugs can occur anywhere but probably the most costly ones happen where no man has gone before and especially when it takes a long time to go there. In 2006, the Mars Global Surveyor had remained operational for almost a decade when a software bug ended its life. A software update threw open a possibility for data to be written to a wrong memory address which in turn caused the solar panels of the Surveyor to get stuck. The Surveyor then made movements to face the sun exposing its battery which overheated and became non-functional.  

15) To find the Ozone hole: Software bugs may not just result in incorrect behavior; they can cause long delays in the calculations. Analysis of atmospheric data by NASA also involves immense calculations. One such project that was launched in 1975 to map the Ozone layer, was designed to ignore values that were the outliers in the expected measurements. The hole in the Ozone was not found until after the data was reviewed. NASA did not find the Ozone hole. It was the British Antarctic company in 1985 that obtained data with a ground based instrument from a measuring station and were the first to find the Ozone hole. 

16) Explosions from bugs: Software bugs are generally reduced with testing and validations in mission critical applications which greatly reduce the risk of running software. However, if the bugs are planted deliberately, hazards do result. In the cold war era, the CIA is said to have slipped the Russians faulty control software to be used for a major gas pipeline which the KGB was stealing from a Canadian company. The bug caused a huge Siberian pipeline explosion in 1982 and the US satellites could observe the explosion and fire from space. 

#codingexercise

In a boolean matrix, find the length of the largest region. A region is a group of cells with value 1 such that each cell is adjacent to another cell also with value 1 and adjacency can be horizontal, vertical or diagonal.

int GetLargest(int[,] M, int row, int col)

{

var visited = new bool[row,col];

int result = int_min;

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

   for (int j =0; j<col;j++)

       if (M[i,j] && !visited[i,j])

       {

           int count = 1;

           DFS(M,i,j, ref visited, ref count);

           result = Math.max(result, count);

       }

return result;

}

// DFS attempts all the eight adjacent cells a d only proceeds to recursion on that when it is safe to do that. Here safe means the cell is a valid position, has a 1 and has not been visited before. All the eight adjacent positions are tried.

This article is a continuation of some more stories on Software Engineering incidents as shared here:

6) Got sick – Hackers let loose virus and other malware programs for the general public to run on their computers but none was more widespread as the Blaster virus which proved a wake up call for Microsoft.  The blaster was so named because it set a registry key with the “msblast.exe” so that it launched everytime Windows starts.

7) Data too -  Following close on heel to Windows, SQL Server was also affected by the Slammer worm. The Slammer worm is a computer worm that caused denial of service on some hosts and slowed down the general traffic. It exploited a buffer overflow bug in Microsoft SQL Server.

8) Cascading failure – Networks are formed by interconnected nodes that talk to one another. As nodes start failing, it might proceed progressively to take the network down. Internet happens to be a network and ISPs are responsible for the bulk of the traffic to route through this network. Many ISPs have experienced outages when their edge routers failed.

9)What’s in a date – The Year 2000 problem was  a computer bug that related to how date was stored where the four digit year was abbreviated to the last two digits and rollover to 2000 meant the clock was reset to 1900.Companies worldwide anticipated and moved quickly to prempt a widespread failure and were large successful.

10) for a Penny – Pennies are very small amount in transactions worldwide and are often rounded resulting in either money gained or lost. When the rounding is done to make a profit and repeated endlessly, it can amount to quite a substantial sum. This may even be noticeable to the human eyes but it is certainly not when the transactions happen between computers and in the background by code that does validation which may be rigged. To the gasoline industry however, the pennies may be very important. In fact gasoline has been sold at a price that ends with 9/10ths of a cent, with retailers rounding up the cost of a gallon to the next penny. But even this is sufficient for the oil industry to rake in millions of dollars in extra profit each month.
#codingexercise
Find the count of numbers formed by subsequences of the digits of a given number n that are greater than a given value m
Void  Combine(List<int> digits, int m, ref List<int> b, int start, int level,  ref List<List<int>> combinations)  
{  
for (int I =start; I < digits.length; I++)  
{   
  if (b.contains(digits[i])== false){  
    b[level] = digits[i];  
    combinations.Add(b);
    if (I < digits.length)  
        Combine(ref digits, ref b, m, start+1, level+1, ref combinations);  
    b[level] = 0;  
}
}
} 
int CountSubsequencesWithValueGreaterThanM(List<int>digits, int m)
{
var b = new List<int>();
digts.ForEach(X => b.Add(0));
int start = 0;
int level = 0;
var combinations = new List<List<int>>();
Combine(digits, m, ref b, start, level, ref combinations);
int count = 0;
var permutations = new List<List<int>>();
Combinations.forEach(x => {
      int i = 0;
      var used = new bool[x.Count];
      var candidate = new List<int>();
      Permute(x, ref candidate, ref used,  ref permutations);
 });
permutations.ForEach(x => {
  if (x.value > m)
     count++;
}
return count;

}

This is a  collection of software engineering incidents that affected a lot of people. They are presented as different themes.
1) When the tower toppled : The Jenga tower of Javascript was a collection of modules used widely by programmers worldwide with a variety of software applications. When one developer unpublished more than 250 of his modules from a popular package manager, there were hundreds of people unable to build and release their software for use in their operations. The developer was peeved when lawyers representing corporation claimed one of his modules was infringing on a brand with a similar name and contacted the admin manager to take away the package from the developer. The developer retaliated with unpublishing his work which included a library used to pad strings with zeros or spaces on the left and this library was used in the core of popular javascript packages. With the dependency gone, the applications failed worldwide. The package manager took a rare step of "un-un-publishing" the required module so that others can carry on with their work.
2) When a typo took services down. A software engineer had a single typo in issuing a command to a take a bunch of servers offline and ended up taking down a lot more including some critical ones in a popular cloud service for storage. Those same critical servers were storing information about other storage objects used by millions of people. Since these servers had never been taken offline, rebuilding them was not even exercised with a disaster management plan and the company had to go on a war footing to make amends.
3) Left the door open – Although software services allow artifacts from users to be available anywhere anytime through online document sharing schemes, they generally exercise little control over what users may upload or inadvertently share with others. Personal medical information are also often stored in spreadsheets and files and these are put up in document sharing portals. A file indexing system then picks the documents up to read its contents and index it to make it easier to find by search when users enter just a few words in a search bar to lookup documents. It turns out that these same medical information was now just a few clicks away for everyone to see.
4) Wake it up- When systems malfunction and the administrators find that there is little information by way of documentation, they bank their hopes on return to normalcy by shutting the system down and waking it up. Generally all systems perform checks and initializations called bootstrap before resuming normal mode of operations.  It turned out that with a glitch in this bootstrap, administrators could take a system down but not could bring it back up as it went into an endless cycle of reboots until finally someone found a way to trick it back to resuming fully.
5) Jump the clock. Software products often work with dates. It is easy to check for events based on time because time is always progressive. However when the time is based on calendar, subtle repetitions may escape attention. This was exactly the case when the leap year extra day was ignored by a popular database server that affected installs worldwide. It was only mitigated by tricking the database server to think it was working a day before the extra day and jumping the clock to the day after.
#codingexercise
Yesterday we were discussing ways to find if there are subsequences of distinct digits that have a sum divisible by m. If we were to enumerate these, it would be as follows:
Void  Combine(List<int> digits, int m, ref List<int> b, int start, int level,  ref List<List<int>> combinations)  
{  
for (int I =start; I < digits.length; I++)  
{   
  if (b.contains(digits[i])== false){  
    b[level] = digits[i];  
    combinations.Add(b);
    if (I < digits.length)  
        Combine(ref digits, ref b, m, i+1, level+1, ref combinations);  
    b[level] = 0;  
}
}
} 
void PrintSubsequencesWithSumDivisibleByM(List<int>digits, int m)
{
var b = new List<int>();
digts.ForEach(X => b.Add(0));
int start = 0;
int level = 0;
var combinations = new List<List<int>>();
Combine(digits, m, ref b, start, level, ref combinations);
Combinations.forEach(x => {
         if (x.Sum() %m == 0){
                x.ForEach(t=> Console.Write("{0},", t));
               Console.WriteLine();
 });
}

Yesterday we were trying to find the subsequence sums that are divisible by m. We noted that we were multiplying the sum of all elements with the sum of binomial coefficients. If one of the two components is divisible by m, then sum of all subsequences would also be divisible by m. In addition we could find the sub patterns to check the divisibility by m. For example we could enumerate subsequences that are individually divisible by m using the combine method with the condition for individual combinations to be added to the result only when their sum is divisible by m.
Another approach we demonstrated was to merely check for the presence of  a subsequence with a sum divisible by m. We translated this problem to find if there is any subset in the sequence that has sum 1x m, 2 x m, 3 x m, ... n x m where n x m <= sequence.sum(). Since we already know how to check if any subsequence has a sum equal to a given value using dynamic programming, this approach merely iterates over the possible candidates to target.

But we could go further into using the patterns of forming subsequences. We do this with the help of modulo because all sums will have to be in the modulo range 0 to m-1. We discuss this approach here.

This alternative way finds the sum of subsets that are divisible by m by recognizing that subsets will have sum whose modulo varies over 0 to m-1. Each element of the input either counts by itself or as  part of a subset. If we populate a boolean DP table for this range of 0 to m-1 and iterate over the elements then each element sets its corresponding cell in the DP table by itself. When it is a part of a sequence, we can repeat the problem considering any of the previous modulos and setting the corresponding cell in the DP table. This subproblem only happens for each of the modulo in the range only once. Therefore the inner loop is linear and we initialize a new sum array prior to iterating. Each cell of this new sum array for 0 to m-1 can be true or false indicating that the DP table for that corresponding index will be set to true because we have now formed a subset.  When we select the candidate modulo in the inner loop per the iteration, the new sum is the displaced modulo by the inclusion of the current element, The selection only happens when the dp entry for the candidate modulo is true and the new sum entry is false indicating we are forming a subset with a prior modulo and a new subset. As subsets keep forming and as the new sums get set with true, each corresponding DP table entry gets set. Eventually we return the value of the cell corresponding to m=0. In fact, we can bail early if we encounter it any sooner. 

static bool HasSubSetSumModuloMEqualsZero(List<int> arr, int n, int m) 
        { 
            if (n > m) 
                return true; 
             var DP = new bool[m]; 
  
             for (int i = 0; i < n; i++) 
             { 
                 if (DP[0]) 
                     return true; 
                 var temp = new bool[m]; 
                 for (int j = 0; j < m; j++) 
                 { 
                     if (DP[j] == true) 
                     { 
                         if (DP[(j + arr[i]) % m] == false) 
                             temp[(j + arr[i]) % m] = true; 
                     } 
                 } 
                 for (int j = 0; j < m; j++) 
                     if (temp[j]) 
                         DP[j] = true; 
                 DP[arr[i] % m] = true; 
             } 
            return DP[0]; 

        }