Showing posts with label programming. Show all posts
Showing posts with label programming. Show all posts

Tuesday, December 9, 2014

Pointer Fun With Binky From Stanford Computer Lab

Stanford created a strange, claymation character named Binky to teach students about the concept of Pointers in programming. Watch the video and share in the severe WTF-ness that comes along with it.

Sunday, November 30, 2014


When UNIX co-progenitor and super-smarty-pants Ken Ritchie was given a Turing Award, he provided a warning to those within ear shot. Admins and developers often find it satisfactory to review the source code of applications to determine maliciousness. And to a certain extent, this works out all right. Over time we have built a series of expectations of where to expect naughty code based on our experience. We have also chosen to trust other types of tools that we use during this process. We discriminate.

But there's no reason that bad stuff *has* to be in the applications that we expect to find it in. Yes, the clever among us know that compilers can be bad. But we check the source of our compilers and find no bad stuff, and so we assume we are safe.

We do, though, compile the compiler, don't we?

Well, alright then some megalomaniac at Intel or somewhere far upstream decided to embed badness in the embedded distro compilation software. We can still look at the binary of compiled programs to determine What Is Really Going On.

We do, though, tend to use applications to help make machine code human readable, though, don't we?

The point to the thought experiment isn't to stop the unbelievable interchange of ideas and applications that has brought us to where we are today in modern computing. It would be impossible to manually read the machine code of all of the applications that we use and still function in the workplace and our other communities as we are expected to.

Rather, we should be aware of the trust that we place in our tools. We should be aware that when we set out to solve or review problems, we take certain things for granted.

The point is not, that we should never trust. The point is that we should make trust decisions willfully and based on reasonable deductions and facts; not impulse or ease of use.

I came across Ritchie's chat today in a CS class, and its still as relevant today as it ever was. You can read the whole thing here.

Wednesday, November 12, 2014

Programming in C - Chapter II - It Really IS Rocket Science

Problems arise with numerical expression in computing. In reality, there are an infinite number of real numbers. However there is clearly not an infinite amount of infinite memory even in the largest of super-computers, and memory that is addressable by an application is only a fraction of the total finite available memory. How to we deal with these obstacles? We will explain more in a moment.

First let's overview in more detail how the C compiler handles numeral types. Consider the application below:

#include <stdio.h>

int main (void)
    float f = 1 / 10;
    printf("%.2f\n", f);
    return 0;

Here we declare a float, 1/10 which should clearly resolve to 0.1 or 0.10 since I am declaring that printf provide a float with two digits after the decimal point. However, upon complation and excecution the program will stubbornly return a value of "0.00".


The issue is that I am declaring a float as an operation of two integers - 1 and 10. As a result, the compiler is performing an "implicit typeset" of the float "f" 0.10; as a result throwing out EVERYTHING after the decimal point (without so much as performing a round function). The truncation occurs before the storage in memory (note this is different from an implicit typeset); as a result the float f is able to store "0" as "0.00" without the compiler presenting an error about a symbol conflict or the wrong variable type. "0" isnt an int; it is a truncated float.

How do we resolve this? The easiest solution is to convert the "int" input into "float" input like so:

int main (void)
    float f = 1.0 / 10.0;
    printf("%.2f\n", f);
    return 0;

Which produces:

#: ./float0

That is not the only resolution, however. We can explicitly cast the input integer into floats like so, by providing the preferred variable type in parantheses () directly in front of the input to be "cast" into the correct type. This is called *explicit typecasting*:

#include <stdio.h>

int main (void)
    float f = (float) 1 / (float) 10;
    printf("%.2f\n", f);
    return 0;

Note that 1 and 10 could just as easily be actual variables in the above example.

Let's return to an earlier example, in which we tried to chan the int inputs 1 and 10 into float inputs 1.0 and 10.0. What happens when we look more closely at the output - for instance, by drawing out the decimal point to 20 places instead of 2, like so?

#include <stdio.h>

int main (void)
    float f = 1.0 / 10.0;
    printf("%.20f\n", f);
    return 0;

The output becomes imprecise:

#: ./float1

Why? Floats, like all of our other variables types, have a finite amount of memory with which they can be addressed and not an arbitrary amount. Thus there is a finite amount of real numbers that can be represented with each float, as we discussed above. The imprecision that we see here is a result of that limitation.

Put another way, we begin to see a core paradox in computing limitation:

There is an INFINITE amount of numbers that computers CANNOT represent with a FINITE amount of bits.

This limitation has real world consequences. The lesson proceeds with a video from the show "Modern Marvels: Engineering Disasters". The video described the June 4th, 1996 launch of an Un-manned Ariane 5 Rocket carrying satellites designed to determine precisely how the Earth's magnetic field interacts with Solar Winds. The rocket was built for the European Space Agency, and was launched from a facility in French Guyana.

37 seconds into the flight, engineers responsible for the launch first determined that something was wrong - the rocket's nozzles were swivelling in a way that they should not have been.

40 seconds into the flight it became clear that the vehicle was in trouble and might not survive the launch. Mission control at that point made a decision to destroy the rocket completely. The rocket, if it had been allowed to fail on its own, could have become a hazard to public safety as parts and components rained down unto homes and onlookers below.

This was the very first launch of the Ariane 5 class rocket, and the failure that occurred was the result of a software issue.

The Ariane 5's software contained a number that required 64 bits to express correctly. The developers intended to convert this into a 16 bit number. They assumed that the number would never be vey big; most of the digits in that 64 bit number would be zeroes. The assumptions about the size of the 64 bit number were wrong.

Most of the software from the Ariane 5 was originally designed for the Ariane 4; in which the software had been successful. The software was carried over to the new model as it had posed no problems in the old model. However, there was a key difference between the two rockets. The Ariane 5 accelerated much faster than the Ariane 4. The 64 bit number described above was a function of acceleration; numbers that remained "mostly zeroes" in the older model were no longer so in the new, faster model.

The Ariane 5 was not the first rocket in which data conversion (or "type casting") errors played a role in modern rocket technology. In 1991, with the start of the first Gulf War, the famous American PATRIOT Missile manufactured by Raytheon Corporation experienced a failure similar to that of the Ariane 5. As a result of the PATRIOT Missile failure, 28 American soldiers were killed and approximately 100 other wounded when a PATRIOT Missile designed to target and destroy incoming Iraqi SCUD missiles did not fire.

The PATRIOT Interceptor was deployed to protect Saudi Arabia and Israel from Iraqi SCUDs in 1991. The PATRIOT is a medium range Surface to Air rocket. The Orwellian acronym stands for Phased Array TRacking Intercept Of Target. The missile is often loaded into a carriage delivery system that is mounted onto the back of a truck. It is designed to be portable; the Patriot is a 20 feet long and weighs 2000 pounds - while the payload itself is a mere 150 pounds. That payload is a high explosive fragmentation device; the casing of the warhead is designed to act as buckshot. The missiles are packed in a container that holds four and loads onto the pack of a semi trailer.

PATRIOTs have a long history; 20 years before they obtained world-fame through the marketing efforts of George Bush Sr. Originally they were thought of as an air-defense battery, to shoot down planes. The anti-missle capability was a new-feature, one implemented to fulfill the military's unique mandates in the Gulf during Round 1 of the Hussein v Bush saga.

SCUDs fly much faster than the average plane: Mach 5. But reaching the right speed was only part of the problem of the sort of upgrade that Raytheon needed to pull off to keep their Pentagon paymasters happy. When the PATRIOT was rushed into service, Raytheon was unaware that the Iraqi military had modified their fleet of SCUDs; making interception much more difficult; close to impossible. Ironicallly enough, the Iraqi modifications were not intended to defeat interception, but to increase the range of the missle from their original 300km to 600km

The modified SCUDs would `wobble` as they flew inbound to their target, maintaining an unstable trajectory. To increase the range of the rockets, the Iraqis had taken weight out of the warhead, which was loaded onto the tip of the SCUD. This unstable trajectory meant that in the overwhelming majority of cases, PATRIOT missles would fly right past the SCUD, missing it entirely.

Once operators of the PATRIOT realized they had missed their mark (which was close to 100% of the time), they detonated the payload remotely as did the mission control for the Ariane 5 - except in this case the operators could not care less about the safety of those below the PATRIOT; they were concerned that allowing the PATRIOT to land would allow the Iraqis to salvage components. Some might view this concern as strange, given that the PATRIOT was at this point completely worthless. Perhaps the Pentagon feared that Iraqi military engineers could succeed where Raytheon corporation had failed? Not quite - the Pentagon filmed these remote detonations and provided them to the credulous Press, who released the footage of giant airborne fireballs while declaring breathlessly that the film represented yet another victorious interception by the PATRIOT missile of one of Saddam Hussein's diabolical SCUD warheads. These clips, filmed exclusively in night-vision, had a blinding glare during the PATRIOT remote detonation; it was during the moment, when the screen was all greenish-white, that the SCUD streaked past, completely undamaged. When the film began again, viewers saw the night sky, empty except for a shower of sparks and debris that they assumed was the mingled destruction of both missiles but contained only the destroyed PATRIOT.

What was in Iraq a failure rate of 100% became a success rate of 100% for the TV audience back in the United States. Support soared for the glorious campaign and its fearless leader, the command-in-chief.

But you can only fool all of the people some of the time. For Gulf War I, the fakery came to a startling and sudden end one night in the desert of Dhahran in Saudi Arabia. There, even the Pentagon spin doctors were not bold enough to replace the uniforms of the dead. There could be no mis-understanding; the PATRIOT missile was a complete and utter failure, a failure that left 28 young Americans dead.

In Dhahran a PATRIOT battery's radar system lost track of an incoming SCUD. The PATRIOT interceptor did worse than miss the incoming missle; it never launched at all. Because of a programming error.

It was clear to anyone paying attention and with the proper access that the Pentagon was completely un-bothered by the apparent madness of conducting a military campaign in which the primary armament was essentially a plastic pistol that when fired produced a flag printed with the cartoon word "BANG!". So it should be no surprise to us that it was not the Pentagon who pointed out and resolved the software glitch killing American soldiers, but the Israelis. The Israeli military first caught on that the longer a PATRIOT missile system remained on, the larger was the time discrepancies in the targeting systems became. The time discrepancies were the result of a clock application in the targeting computer.

At two weeks before the debacle in Dhahran, the Israelis reported to the Defense Department that the PATRIOT computers "lost" time. After about 8 hours of operation, the system became significantly less accurate. DoD, in their infinite wisdom, responded to the Israeli warning by telling all PATRIOT operators to regularly reboot their targeting computers. The DoD failed to specify how long the PATRIOT should remain online before a reboot; this crucial detail was left as an excerise for the reader. 8 hours? 10 hours? 1000 hours? The operators did not know what the Israelis knew - that there was a very specific window of operation after which the PATRIOT would fail to even appear functional.

The PATRIOT missle battery in Dhahran had been online continuously for 100 hours on the night of February 25th, 1991.

The targeting computer clock was designed to track time to an accuracy of 1/10th of a second. Unfortunately, fractions cannot directly and exactly be expressed in binary.

For example, lets consider the example of 1/3 (or one third). As a decimal number, we cannot exactly express 1/3 - it is a repeating decimal, 0.333333[...], where .3 repeats infinitely. Because computers have a finite amount of memory, the infinite decimal version of 1/3 cannot accurately be represented.

It is this issue that impacted the PATRIOT as it attempted to calculate values represented by fragments of a second. And due to the design of the PATRIOT's flawed application, the errors compounded over time.

After 100 hours of continuous operation, the time measurement flaw had compounded to a misrepresentation of time values by one third of a second. Not long under ordinary circumstances - but a lifetime for a SCUD missile travelling at Mach 5. At Mach 5 a targeting error of 1/3 of 1 second resulted in a trajectory miscalculation of 600 meters.

Immediately preceding the Dhahran catastrophe, a SCUD launch was detected by early warning satellites orbiting the Earth. The satellites were able to predict a general trajectory of Dhahran for the location of the SCUD's impact, but not exactly where it would hit. The PATRIOT's radar system was designed to calculate the missing part of the trajectory and fire an interception missile. The PATRIOT radar system would send a radar pulse, and based on that pulse was designed to format a prediction of the location of the SCUD at the time of the next radar pulse. Such a prediction simulation is referred to as a "range gate". The PATRIOT would then correct its next prediction based on the results, and do so several times; this prediction information would form the basis of the PATRIOT missile's own targeting solution. After all, the PATRIOT missile had to be pointed at where the SCUD *would* be after a given interval of time based on the speed of both the PATRIOT and SCUD; not where the SCUD *was* at the time of the launch of the PATRIOT missile.

It is not difficult to see how absolutely vital an accurate clock is to the proper function of such a system. Even worse, there was an additional "feature" of the PATRIOT radar system that ensured that the malfunctioning clock would result in disaster at Dhahar.

At any given time, there are a multitude of objects flying through the air. Birds. Clouds. In a war zone, there are friendly military aircraft. On top of this is the fact that radar is not, in itself, a flawless data input system. Radar systems are not unknown to produce blips that do not correspond to physical objects for all sorts of reasons.

As such, the PATRIOT system had to have a function for error detection - it just wouldn't do to launch a 2,000 pound missle at a flock of geese. To this end, the targeting computer had a window during which trajectory calculation would occur. If an object remained in this window, trajectory calculation would continue. If, however, an object did not appear within the window than the PATRIOT would dismiss further calculation and label prior input as a false positive. With such a function, again, correct time calculation is absolutely critical. At Dhahrar, the broken time calculator let the PATRIOT battery to look in the wrong areas to calculate its range gate. When the SCUD failed to appear within the range gate, the PATRIOT dismissed prior input as a false positive; when in fact the SCUD was still on its way, but one third of one second outside of where the PATRIOT was looking for it.

The incoming SCUD bypassed the PATRIOT defense battery, slamming directly into its intended target - a military barracks housing hundreds of American soldiers.

All because of incompetent type casting within the PATRIOT targeting application; and furthermore due to the absolutely unethical handling of those software issues by the Defense Department, who knew long in advance of the critical failures of the PATRIOT system but did not take proper action to inform the soldiers whose lives depended on the PATRIOT. Perhaps Pentagon officials feared that explicit orders to replace the software would cause a publicity disaster for those involved with the procurement of the PATRIOT system and their friends at Raytheon. There is no other explanation for the DoD's actions, besides perhaps acknowledging that the DoD cannot function in even the most basic and vital of bureaucratic tasks - that the Pentagon excels in buying war toys and marketing wars but is completely incompetent in the waging of war. Both options, as of the date of this writing, strike the author as equally feasible.

The SCUD missile that destroyed the Dhahran military barracks in Saudi Arabia was the last SCUD successfully fired by Saddam Hussein during the first Gulf War.

Perhaps I am being too harsh on the Pentagon and their pals at Raytheon. A software patch for the PATRIOT missile targeting system was in fact built and delivered to the front. It arrived in Dhahran on February 26th, 1991 - the day after the barracks were destroyed.

***NOTE: This is the Second Chapter of an ongoing series published here on Programming in C which is based upon the Harvard Class CS50. Content here from that class is published solely for educational purposes; I see no profit through the publication of this website including advertising. A good portion of today's post includes content from the show "Modern Marvels", parts of which are transcribed here - again only for the fair use of educational purpose. All barbs, jokes, political statements and assignations of responsibility for the Dharar disaster are entirely my own and not the opinions of Harvard or "Modern Marvels".

Friday, November 7, 2014

Programming in C - Before We Get Started

Requirements | Framework | POSIX

Recently I have been spending quite a bit of time learning how to program in C. It has been quite a few years since I have had anything to do with C, spending most of my time in a very different OSI layer entirely. Even when I did come across it some time ago, I was never anything but barely competent - this ignorance on my part has always disturbed me, and so I have endeavored to do something about it.

Currently I am taking a few computer science classes at Harvard University; it is my plan to summarize a portion of what I have taken from those classes concerning the C programming language here on my website for readers who are interested.

For readers with an advanced knowledge of C, these readings could be viewed as refresher courses. The content, although filtered through my humble brain, will be entirely the result of knowledge acquired through Harvard, so my hope is that even for the experienced C hacker there may be something of interest.

For the layman, the content should be easily digestible. We will include plenty of links and such for further reading. And as always, readers are encouraged to leave comments or contact me directly should you have any questions about the material covered here.

In order to get started, you will require a software development environment that allows you to compile and execute programs written in C. If your computer runs Linux - congratulations! You already have this. If you have a Windows computer, you should probably download MinGW, which I explain in greater detail below. Mac users should install xcode, which includes the clang compiler and a variety of other development tools. LLVM is another option for users of a variety of operating systems.

You will also need a compiler. With Windows, installing MinGW takes take of this for you by including the gcc compiler compilation with the installation package. For Linux users, I recommend installing either clang or gcc. The commands to do this depend on your distribution. BSD users should already have clang as part of their OS. I've included a couple of command examples below to install clang, or you can check out more comprehensive documentation through the LLVM project.

#sudo yum install clang

#sudo apt-get install clang

Don't I need a special computer to use C?

No! While I use the Red Hat flavor of Linux as my operating system-of-choice for development, you can just as easily use any old computer that you wish. Windows users, for example, have a variety of options available to them to prepare an environment for C. The two options that I prefer, depending on the project, are Cygwin and MinGW.

What is Cygwin?

The developers of Cygwin describe their project as having two primary components. First, Cygwin contains a large collection of GNU and Open Source tools which provide functionality similar to a Linux distribution on Windows. Second, Cygwin has a DLL (cygwin1.dll) which provides substantial POSIX API functionality. Cygwin provides a huge and diverse amount of functionality through its library of third party downloads (way too much to list here).

What is MinGW?

MinGW stands for "Minimalist GNU for Windows". As the name suggests, MinGW provides a very minimal software development interface for native-Windows applications. If you wish to learn how to program C using nothing other than a Windows computer MinGW is absolutely the tool of choice. This is because MinGW requires no third party libraries or other add-ons to get going; all that MinGW needs is the native C runtime library included with Windows, MSVCRT.DLL, and a few other native Windows DLLs.

MinGW ships with a Windows port of the gcc compiler, which lets you compile not just applications written in C, but also C++, ADA and FORTRAN if you are so inclined (C++ is great, but if you are writing FORTRAN applications in 2014, seek professional help immediately). It gives you a linker so you can write your own libraries, an assembler, and an archive manager. 

In summary - for learning how to program C on your Windows computer (especially if you want to create programs that run natively in Windows), MinGW is the tool to use.

What is POSIX? 

POSIX stands for "Portable Operating System Interface". POSIX is a set of standards for applications to ensure interoperability between operating systems.

In theory, an application that is completely POSIX compliant can be run on any OS that is also POSIX compliant. In practice, very few Operating Systems are entirely POSIX compliant. Those that are fully compliant are not widely used outside of big businesses. Some examples of fully POSIX compliant Operating Systems that you may have used or heard of are: Solaris (originally created by AT&T and Sun Microsystems, now owned by Oracle) and HP-UX (Hewlett Packard's proprietary version of Unix). Other examples that are less widely known are AIX, IRIX, RTEMS and A/UX. As you can see, these operating systems tend to share certain characteristics. They are mostly closed source, owned by massive corporations, and designed to work with proprietary hardware. 

Most commonly used Operating Systems are partially POSIX compliant. Most versions of Linux and BSD fall within this group. 

Windows is partially POSIX compliant through the use of a compatibility feature set or a third party application. Cygwin is the application of choice for Windows POSIX compatibility, but it is not the only option. Other applications that provide similar functionality are UWIN (from AT&T Research Labs) and MKS Toolkit (by MKS Inc).  

Windows users may also opt to install an additional subsystem, rather than an application or API, in order to enable a POSIX-compliant environment. Until Windows 2000, Windows NT users could install the frankly-named "Microsoft POSIX subsystem" to enable partial POSIX compatibility. A now-defunct company, Softway Systems, built on top of the Microsoft POSIX subsystem to develop a fully POSIX compliant environment for Windows called Interix. With the relase of Windows 2000, Microsoft provided the Windows Services for UNIX, or SFU (a sly insult to users, perhaps?), also referred to as the Subsystem for UNIX-based Applications or SUA. 

Services for UNIX changed the game quite a bit for developers using Windows, providing a much more functional and less buggy application interface for developers. This is also the current Microsoft-provided POSIX solution as of Windows Server 2012 / Windows 8 (as of this writing Windows 10 is still pre-alpha). As with Cygwin, Services for UNIX provides a whole heap of functionality beyond a simple POSIX-compatible development environment, almost all of which is outside the scope of our discussion. We may return to SFU in the future, as it deserves its own series of posts and explanations. Users are welcome to install this - just follow the instructions provided by Microsoft.

From here on out we will take for granted that our readers have a POSIX-compliant development environment, including the standard C libraries (stdio.h, for example) and a compiler or . 

Saturday, November 1, 2014

Scratch from MIT & Back to School

As time goes on, having a knowing how to write in a programming language is becoming less of an odd and obscurantist lifestyle choice and more of a necessity for gainful employment. Already, anyone wanting to pursue a career in the hard scientists will be finding themselves either developing or working with custom applications. But even entry-level and intern positions frequently have a "please help us with our website / CMS / database" component to them.

The trouble is, people are terrified of code; even very smart people. It looks like ancient greek. For students of ancient greek it looks like Farsi. For Persian students of the Asiatic classics it looks like, err, English, probably. My point is that going from using the internet for Facebook and using the internet for push requests on Github has a very steep learning curve. So steep that most people fall right the hell off the curve.

Enter Scratch. Scratch is an object oriented programming language developed by the Smarty Pantses at MIT. What makes Scratch unique is that every component of the language is graphical; each variable and operand is a colorful building block that you can stick together in your Browser's Flash player, like puzzle pieces. Each puzzle piece only fits together when the instructions that those pieces represent can follow one another logically.

There is a lot here for the layman to enjoy - plenty of plain English Help documentation, sets of components that are based entirely around easy to understand concepts (like motion, for example), and a surprisingly active community of people who are posting some pretty amazing projects with a very limited array of tools. Some clever folks have even made very limited OS emulators.

I came across Scratch myself because I have started taking a few classes at Harvard. Despite a career working as a systems administrator, when I first attended university almost 15 years ago I was fairly certain that I would end up a humanities teacher. Most of my first go round at school was spent with the classics and modern analytic philosophy

The philosophy bit, while never ceasing to get a laugh out of co-workers, has ended up being directly applicable to my career. Having an in depth Ludwig Wittgenstein's logic tables has been very useful when dealing with arrays, for example. The writers that held the most interest for me were logicians - Boole, Whitehead, Russel; people whose work formed the original building blocks of what is now Computer Science.

Anyway, I'm getting ahead of myself. So - I'm taking some classes at Harvard. Because I was a humanities concentrator, I find myself back at the basics. Intro to Computer Science I, or CS50; which has now overtaken Intro to Economics as the largest class in the entire school. Everyone wants their own f*cking `start-up`, I'm sure.

So the first week of this course had me and about 800 eager young minds getting briefed on MIT's Scratch and writing teeny little scratch applications.

Many, many years ago, when I was a very young lad, I had a very special relationship with computers. Things were much different then. Simply knowing how to operate the thing for any task other than word processing made you a bit special (not always in a good way). I had an acoustic coupler and a toshiba *laptop* with dual floppy drives. I could log onto BBS from pay-phones with my coupler. But before I could do even that, there was "Gorillas" and there was QBASIC. Each line of instructions with its only little number in front so the computer didn't get confused. I pored over each line of Gorillas to see how it worked. I broke it; I fixed it; I changed the color of the Gorillas. I made the bananas go faster.

What I'm getting at here is that early Microsoft crap gets me a bit misty eyed and nostalgic. So for my first week project, I made a clone of Windows 95-era Microsoft paint that I named "simple_paint". The pencil, brush, eraser, paint can and circle tool work; the default is the pencil - just click the icon of the tool you want to use from the toolbar on the left, just a you would in the original MS Paint. All of the colors at the bottom work, and the current color icon works, too. Be gentle, its my very first go at using Scratch, and quite a middling example of what can be accomplished. For example, here is a much better example of how to use Scratch to create a wee graphics application.

As time permits, why not give it a go and see what you can make? You can also "remix" my editor if you think you can do better. Start off by using my code base and go from there (a remix is what they call a branch in the super-cool Scratch community).

This is all highly recommended for teachers and educators, btw. If I had come across this as a kid ... it would have changed things. Scratch is completely unintimidating and the ease with which users can begin assimilating and building onto otherwise complex topics is very cool and very unique.

UPDATE: Getting into Harvard can be tough. That's why I will be posting all of my course notes and projects for my classes online. If you can't make a class, or got course materials online but can't attend lectures, or just missed a lecture, you are welcome to get your notes here!

NSA Leak Bust Points to State Surveillance Deal with Printing Firms

Earlier this week a young government contractor named Reality Winner was accused by police of leaking an internal NSA document to news outle...