08 Thursday May 2014
Posted in Programming, Reverse Engineering, Software Development
Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it.
Brian Kernighan
29 Sunday Dec 2013
Posted in Programming
Tags
There has been a lot of discussion lately on the importance of learning to code. And I have added my two-cents. Maybe three.
Here is an interesting opposing viewpoint: You don’t need to learn to code and other truths about future careers. It is the only opposing view I have seen so far. The author argues that coding is not for everybody. If you hate coding, then forcing yourself to learn just to stay competitive in the job market, would be a miserable way to go. And you are not likely to be successful in a job you hate.
Secondly, learning to program just to launch a career change is likely to end in frustration. Going from no programming experience to a programming job, while not unheard of, is rare. Many tech companies today have a grueling application process requiring you to demonstrate proficiency and that takes years to master. Up to 10 years in some studies I have seen.
It is always good to hear the other side of an argument. Learning to program may not be great career advice. However, what is the harm in learning for fun? For your own personal benefit? Programming is not some big mysterious skill that can only be done by a few hoodie clad brainy types. Anyone can learn to code and some languages are remarkably easy pick up. While it may take a decade for mastery, the fundamentals can be picked up in as little as a few weeks. And you can create some amazing things almost right away. There is no reason not to try your hand at programming. See if you like it. Creating your own web-sites or apps can be fun even if no one ever sees your creations.
To actually learn how to think. I think everyone in this country should learn to program a computer. Everyone should learn a computer language because it teaches you how to think. I think of computer science as a liberal art.
Steve Jobs from the lost interviews
Speaking from personal experience, programming has sharpened my problem solving skills and it will sharpen yours too. Becoming a better problem solver is a skill that will benefit everyone. No matter the job market situation: if you can solve problems then you will always have a job. The market is already flooded with people that cause problems, but we could always use a few more problem solvers.
23 Monday Dec 2013
Posted in Computer Science, Philosophy, Quine programs
Tags
While at a Christmas party, I met a Computer Science undergrad currently earning his degree at UNM. He was having trouble grappling Quine programs. A Quine program is a computer program that takes in no input, and produces a copy of its own source code as the only output. That is — self-replicating code. It is not as easy to explain as one might think, and my poor crude attempts at doing so only confused this poor CS student further. To my defense, I used examples you can find online, but many of these examples are not very intuitive to understand. Take for example this Quine written in Python:
s='s=%r;print s%%s,';print s%s,
Fire up a Python interpreter and try it out. It simply prints that exact line you typed in. Unless you are very familiar with Python strings and the string formatting codes, it is hard to see how this program works. But it is essentially, defining a string s, then using that string itself to replicate. Here is a Quine written in the old Kernigan and Ritchie C style:
main(){char*s="main(){char*s=%c%s%c;printf(s,34,s,34);}";printf(s,34,s,34);}
I don’t believe it will compile with today’s C99 or better compilers, which don’t allow programmers to implicitly call the printf function with out using:
#include <stdio.h>
Again, the C program is not any more intuitive to understand than the Python example. So today, my goal is to write a Quine program in C that is easier for me to explain by example. Instead of using printf format strings, I am going to leverage the power of a computer’s ability to represent C source code as data. The goal is to take the data representation of the source code and print it, then translate the data into the ASCII high-level source code and print that. After some trial and error, here is what I came up with:
#include <stdio.h>
int
main (void)
{
unsigned int i;
printf("const unsigned char data[] = {");
for (i = 0; i<sizeof(data); i++)
{
if (i%8 == 0)
printf("\n");
printf("%0#4x,", data[i]);
}
printf("\n};\n\n");
for (i = 0; i<sizeof(data); i++)
putchar(data[i]);
return 0;
}
The above is my partial program so far. There are two for-loops. The first loop will iterate through a byte array called data, which I have not defined yet because this data array will contain the hexadecimal representation of this ASCII code (i.e. everything from the #include to the last right curly-brace at the bottom).
The second for-loop takes that same data array and uses the C library putchar that will translate the hexadecimal representation into an ASCII character, which will give us all that C code from the #include to the last right curly-brace at the bottom. In other words: this source code will print an exact copy of the data array and our source code when executed.
Next, we need to translate our C code into the byte array data and place it at the top of our program (before the #include statement in the source above). It should look like this:
const unsigned char data[] = {
0x23,0x69,0x6e,0x63,0x6c,0x75,0x64,0x65,
0x20,0x3c,0x73,0x74,0x64,0x69,0x6f,0x2e,
0x68,0x3e,0x0a,0x0a,0x69,0x6e,0x74,0x0a,
0x6d,0x61,0x69,0x6e,0x20,0x28,0x76,0x6f,
0x69,0x64,0x29,0x0a,0x7b,0x0a,0x20,0x20,
0x20,0x20,0x75,0x6e,0x73,0x69,0x67,0x6e,
0x65,0x64,0x20,0x69,0x6e,0x74,0x20,0x69,
0x3b,0x0a,0x20,0x20,0x20,0x20,0x0a,0x20,
0x20,0x20,0x20,0x70,0x72,0x69,0x6e,0x74,
0x66,0x28,0x22,0x63,0x6f,0x6e,0x73,0x74,
0x20,0x75,0x6e,0x73,0x69,0x67,0x6e,0x65,
0x64,0x20,0x63,0x68,0x61,0x72,0x20,0x64,
0x61,0x74,0x61,0x5b,0x5d,0x20,0x3d,0x20,
0x7b,0x22,0x29,0x3b,0x0a,0x20,0x20,0x20,
0x20,0x66,0x6f,0x72,0x20,0x28,0x69,0x20,
0x3d,0x20,0x30,0x3b,0x20,0x69,0x3c,0x73,
0x69,0x7a,0x65,0x6f,0x66,0x28,0x64,0x61,
0x74,0x61,0x29,0x3b,0x20,0x69,0x2b,0x2b,
0x29,0x0a,0x20,0x20,0x20,0x20,0x7b,0x0a,
0x20,0x20,0x20,0x20,0x20,0x20,0x20,0x20,
0x69,0x66,0x20,0x28,0x69,0x25,0x38,0x20,
0x3d,0x3d,0x20,0x30,0x29,0x0a,0x20,0x20,
0x20,0x20,0x20,0x20,0x20,0x20,0x20,0x20,
0x20,0x20,0x70,0x72,0x69,0x6e,0x74,0x66,
0x28,0x22,0x5c,0x6e,0x22,0x29,0x3b,0x0a,
0x20,0x20,0x20,0x20,0x20,0x20,0x20,0x20,
0x70,0x72,0x69,0x6e,0x74,0x66,0x28,0x22,
0x25,0x30,0x23,0x34,0x78,0x2c,0x22,0x20,
0x64,0x61,0x74,0x61,0x5b,0x69,0x5d,0x29,
0x3b,0x20,0x20,0x20,0x20,0x0a,0x20,0x20,
0x20,0x20,0x7d,0x0a,0x20,0x20,0x20,0x20,
0x70,0x72,0x69,0x6e,0x74,0x66,0x28,0x22,
0x5c,0x6e,0x22,0x7d,0x3b,0x5c,0x6e,0x5c,
0x6e,0x22,0x29,0x3b,0x0a,0x20,0x20,0x20,
0x20,0x66,0x6f,0x72,0x20,0x28,0x69,0x20,
0x3d,0x20,0x30,0x3b,0x20,0x69,0x3c,0x73,
0x69,0x7a,0x65,0x6f,0x66,0x28,0x64,0x61,
0x74,0x61,0x29,0x3b,0x20,0x69,0x2b,0x2b,
0x29,0x0a,0x20,0x20,0x20,0x20,0x20,0x20,
0x20,0x20,0x70,0x75,0x74,0x63,0x68,0x61,
0x72,0x28,0x64,0x61,0x74,0x61,0x5b,0x69,
0x5d,0x29,0x3b,0x0a,0x20,0x20,0x20,0x20,
0x72,0x65,0x74,0x75,0x72,0x6e,0x20,0x30,
0x3b,0x0a,0x7d,0x0a,
};
Now, how did I get the above? Well, we can use an ASCII table and transcribe our C source above by hand… # = 0x23, i = 0x69, n = 0x6E, c = 0x63, l = 0x6C, u = 0x75, d = 0x64, e = 0x65, spaces = 0x20, newlines = 0x0A, etc. That is a lot of work. Being a lazy computer scientist, I wrote the following python script to do it for me:
import sys
f = open(sys.argv[1], 'r')
s = ''
for line in f:
for l in line:
s += '0x%02x' % ord(l)
s += ','
s += '0x0a,'
step = 40
for i in range(0, len(s), step):
line = s[i:i+step]
print line
In the above, you pass in the C file of our first code listing above, and it prints to the screen:
0x23,0x69,0x6e,0x63,0x6c,0x75,0x64,0x65, 0x20,0x3c,0x73,0x74,0x64,0x69,0x6f,0x2e, 0x68,0x3e,0x0a,0x0a,0x69,0x6e,0x74,0x0a, 0x6d,0x61,0x69,0x6e,0x20,0x28,0x76,0x6f, 0x69,0x64,0x29,0x0a,0x7b,0x0a,0x20,0x20, 0x20,0x20,0x75,0x6e,0x73,0x69,0x67,0x6e, 0x65,0x64,0x20,0x69,0x6e,0x74,0x20,0x69, 0x3b,0x0a,0x20,0x20,0x20,0x20,0x0a,0x20, <-------snipped-----------------------> 0x28,0x64,0x61,0x74,0x61,0x29,0x3b,0x20, 0x69,0x2b,0x2b,0x29,0x0a,0x20,0x20,0x20, 0x20,0x20,0x20,0x20,0x20,0x70,0x75,0x74, 0x63,0x68,0x61,0x72,0x28,0x64,0x61,0x74, 0x61,0x5b,0x69,0x5d,0x29,0x3b,0x0a,0x20, 0x20,0x20,0x20,0x72,0x65,0x74,0x75,0x72, 0x6e,0x20,0x30,0x3b,0x0a,0x7d,0x0a,
You can copy and paste that into your
const unsigned char data[] = {
},
block and put that above the #include of the first code listing above. I used Eclipse-C++ to code and run my program. Upon execution the program should print to the console:
const unsigned char data[] = {
0x23,0x69,0x6e,0x63,0x6c,0x75,0x64,0x65,
0x20,0x3c,0x73,0x74,0x64,0x69,0x6f,0x2e,
0x68,0x3e,0x0a,0x0a,0x69,0x6e,0x74,0x0a,
0x6d,0x61,0x69,0x6e,0x20,0x28,0x76,0x6f,
0x69,0x64,0x29,0x0a,0x7b,0x0a,0x20,0x20,
0x20,0x20,0x75,0x6e,0x73,0x69,0x67,0x6e,
0x65,0x64,0x20,0x69,0x6e,0x74,0x20,0x69,
0x3b,0x0a,0x20,0x20,0x20,0x20,0x0a,0x20,
0x20,0x20,0x20,0x70,0x72,0x69,0x6e,0x74,
0x66,0x28,0x22,0x63,0x6f,0x6e,0x73,0x74,
0x20,0x75,0x6e,0x73,0x69,0x67,0x6e,0x65,
0x64,0x20,0x63,0x68,0x61,0x72,0x20,0x64,
0x61,0x74,0x61,0x5b,0x5d,0x20,0x3d,0x20,
0x7b,0x22,0x29,0x3b,0x0a,0x20,0x20,0x20,
0x20,0x66,0x6f,0x72,0x20,0x28,0x69,0x20,
0x3d,0x20,0x30,0x3b,0x20,0x69,0x3c,0x73,
0x69,0x7a,0x65,0x6f,0x66,0x28,0x64,0x61,
0x74,0x61,0x29,0x3b,0x20,0x69,0x2b,0x2b,
0x29,0x0a,0x20,0x20,0x20,0x20,0x7b,0x0a,
0x20,0x20,0x20,0x20,0x20,0x20,0x20,0x20,
0x69,0x66,0x20,0x28,0x69,0x25,0x38,0x20,
0x3d,0x3d,0x20,0x30,0x29,0x0a,0x20,0x20,
0x20,0x20,0x20,0x20,0x20,0x20,0x20,0x20,
0x20,0x20,0x70,0x72,0x69,0x6e,0x74,0x66,
0x28,0x22,0x5c,0x6e,0x22,0x29,0x3b,0x0a,
0x20,0x20,0x20,0x20,0x20,0x20,0x20,0x20,
0x70,0x72,0x69,0x6e,0x74,0x66,0x28,0x22,
0x25,0x30,0x23,0x34,0x78,0x2c,0x22,0x20,
0x64,0x61,0x74,0x61,0x5b,0x69,0x5d,0x29,
0x3b,0x20,0x20,0x20,0x20,0x0a,0x20,0x20,
0x20,0x20,0x7d,0x0a,0x20,0x20,0x20,0x20,
0x70,0x72,0x69,0x6e,0x74,0x66,0x28,0x22,
0x5c,0x6e,0x22,0x7d,0x3b,0x5c,0x6e,0x5c,
0x6e,0x22,0x29,0x3b,0x0a,0x20,0x20,0x20,
0x20,0x66,0x6f,0x72,0x20,0x28,0x69,0x20,
0x3d,0x20,0x30,0x3b,0x20,0x69,0x3c,0x73,
0x69,0x7a,0x65,0x6f,0x66,0x28,0x64,0x61,
0x74,0x61,0x29,0x3b,0x20,0x69,0x2b,0x2b,
0x29,0x0a,0x20,0x20,0x20,0x20,0x20,0x20,
0x20,0x20,0x70,0x75,0x74,0x63,0x68,0x61,
0x72,0x28,0x64,0x61,0x74,0x61,0x5b,0x69,
0x5d,0x29,0x3b,0x0a,0x20,0x20,0x20,0x20,
0x72,0x65,0x74,0x75,0x72,0x6e,0x20,0x30,
0x3b,0x0a,0x7d,0x0a,
};
#include
int
main (void)
{
unsigned int i;printf("const unsigned char data[] = {");
for (i = 0; i<sizeof(data); i++)
{
if (i%8 == 0)
printf("\n");
printf("%0#4x," data[i]);
}
printf("\n"};\n\n");
for (i = 0; i<sizeof(data); i++)
putchar(data[i]);
return 0;
}
You should be able to copy and paste the print out into an IDE, compile and run it. Quines are pretty neat. I enjoyed this little exercise. It made me think about levels of meaning; about values and their representations. Computers and programs can’t differentiate between data and code. It is the context that determines when data is meant to be interpreted as code instead of data, and when code is meant to be data (e.g. when downloading a binary file from the Internet). This is an important concept in computer security. It is the fact that we can use data as code that makes shellcode exploits possible.
“Yields falsehood when preceded by its quotation” yields falsehood when preceded by its quotation.
–Quine’s paradox
07 Saturday Dec 2013
Posted in Computer Science, Learning, Programming
Teaching students programming and computer science one hour of code at a time. Here is the official site where you can learn how to become involved. I thought I would take an opportunity here to make my contribution. In this lesson, I will use as my guide, a great introductory to Computer Science (CS) text, often referred to as the “purple” book, or the “wizard” book.
Computer science is really a misnomer. It is not a science. We don’t study a system, observe phenomena, and run experiments to validate a hypothesis. Computer science is not a study of computers anymore than biology is the study of microscopes. A computer is simply a tool. And computational devices come in many different forms. There are the silicon-based binary gadgets that you use everyday, like laptops, tablets, and smart phones. But they are poor imitations of the most powerful computing device ever created: the human being. We are a bio-mechanical machine, performing our computations in base 10. And of course, we are capable of much, much more.
Computer science is not a science; it is more of an art — an engineering practice. Computer science is really about knowledge. The knowledge of how to do something: solve a problem, perform a task in a methodical, mechanical process. This process is called imperative knowledge. It is the knowledge of how to do something. Declarative knowledge, on the other hand, deals with the facts. Let me illustrate with an example found in the purple book.
An example of declarative knowledge:
? How can we use the above declarative knowledge to figure that out? And that is the problem of declarative knowledge. It doesn’t tell you how to calculate the square root of 2 — or how to find the square root of any number. The declarative statement can only tell you how to recognize a square root if you saw one.To solve the square root of any number, we will use a very old algorithm called Newton’s method. Ironically, the method starts with a wild-ass guess (a WAG, we call it in the scientific and engineering community). Then we refine our guess with successive approximations until we get to an answer that is good enough for government work. Let’s construct our algorithm based on Newton’s method:
To find the approximation of the square root of x:
Simple, right? Don’t take my word for it. Try it out.
Compare the 1.4142 with your calculator’s square root button. You should see the 1.4142 plus a bunch of other numbers. We solved out to four decimal places (to the 10-thousandths place), and that is good enough for us.
Now let us write this out as a recipe of instructions:
Square Root X:
- Make a guess G
- Is it good enough?: absolute_value(G*G – X) < 0.0001 then G is the answer and we can stop; otherwise go to next step
- Improve guess G: G = (G + X/G)/2
- Repeat step 2.
So let’s step through our recipe. First make a Scientific Wild-ass Guess.
Next we test our guess by, first squaring our guess and subtracting that guess with X. We take the absolute value because your guess may be less than the square. For example, in the square root of 2, our first guess was 1. 1 – 2 = -1 and we don’t want a negative number because we are measuring the distance between our guess and the perfect square X. And since negative distances don’t make sense, we take the absolute value, which means we first remove the negative sign, and then see if the answer is within some threshold of tolerance. In this case, less than one-ten-thousandths. Or put another way, we will keep refining our guesses until we calculate the square root to four decimal places. If our guess is less than our threshold, then we stop and G is our answer. If not, we go to step three to improve our guess and repeat the process.
Try our recipe above out with a piece of paper and a calculator and see if you get the same results as in the table above, if you let X = 2.
If you made it this far, my dear reader, I want to congratulate you. Together we wrote a computer program. Our program is not in a traditional computer language like C, or C++, or even Python. But it is in the language of English and math. Any reasonably intelligent human computer, with some knowledge of middle school, or high school math should be able to follow our recipe (algorithm) and effectively become the square root button on a calculator.
I hope the above example gives you an idea of what programming and computer science is about. Now, if you really want to learn a programming language, first pick a language and a site you can learn from. I recommend code academy and the language of Python. Python is very easy to learn. Once you get the basics and the syntax down, see if you can take our little recipe above and translate it into your new language, and get a computer to do all this hard math stuff for us.
27 Wednesday Nov 2013
Posted in Programming, Software Development
Been reading a lot about the healthcare.gov software development headaches lately. I am using it as a personal case study of how/when/why software development goes wrong, and how I might be able avoid these issues in any of my projects at the labs. I have been using the Mythical Man-Month (MMM) as my guide and it is very enlightening how one can learn by observing the examples or misfortunes of others.
I would seek out the expertise of anyone who has had the experience of rolling out a massively wide scale web service. Hmmmm… who could that be? Amazon.com immediately comes to mind. I am very surprised that the administration didn’t seek them out. I am not privy to the bidding process so maybe they did; maybe they didn’t. I get the sense (and this is just my opinion) the administration believes that if you throw a bunch of tech-savvy people at a problem, magical and amazing things will happen. Obviously that is not always the case and it violates of one of the tenets of MMM. Another idea: tour several silicon valley companies; how do they utilize the power of the tech-savvy to create amazing things?
Seeking the guidance of an experienced expert, such as Amazon is also a great way to improve your programming skills. I had the opportunity to meet a few developers at the Amazon booth at a security conference last August. They had these programming puzzles similar to below (can you spot the issues?):
wchar_t *fillString(wchar_t content, unsigned int repeat)
{
wchar_t *buffer;
size_t size;
if (repeat > 0x7fffffffe)
return 0;
size = ( repeat + 1 ) * sizeof content;
buffer = (wchar_t *) malloc ( size );
if ( buffer == 0 )
return 0;
wmemset(buffer, content, repeat);
buffer[ repeat ] = 0;
return buffer;
}
They had many of these and I had fun solving them; learned some new programming techniques in the process. I thought: wouldn’t this be a great way to learn how to program? What if we compiled a puzzle book of code with various topics and challenges? One chapter could be on proper syntax and constructs to help with spotting common errors and to teach debugging strategies. Another chapter could be on pointers where you play the role of the compiler/computer and “run” the program to see if you understand pointer arithmetic. A chapter on simple data structures where you draw out the logical implementation of a linked-list or a hash table. And of course a chapter on security with snippets like those above. And if we could format the book in such a way that at the start, you are ignorant of the language, but by the end, you could start using your new skills to make things.
I have several friends who play chess and they use puzzle books to improve their game play. They claim they learn how to spot patterns for end-game scenarios and how to mate in 3 or 4 moves. Perhaps we could do something similar but with code. Perhaps I should consult Amazon.com and see if any such books already exist.
23 Saturday Nov 2013
Posted in Uncategorized
Hello world. When learning to program, or when learning a new programming language, people often write a simple “hello world” to get started. In the tradition of learning a new “programming” environment — this is my “hello world” post.
