## Algorithms & Data Structures Day #2

Sorry for taking the time, I know I said I’ll post a day-after-day guide to algorithms and data structures but you’ll have to excuse me, I’ve been ill.

So on day #1 we talked about linked lists. If you don’t remember what linked lists are you might want to go back to previous post and go over it before diving into today’s guide since we’re going to talk about the stack and how to implement it using linked lists.

First things first:

In computer science, a stack is an abstract data type that serves as a collection of elements, with two principal operations: push, which adds an element to the collection, and pop, which removes the most recently added element that was not yet removed.

But what is so special about the stack? what differentiates the stack from other data types?  The stack has a special way to store and organize data. It follows a simple “rule” called LIFO  (Last IFirst Out). This means that the item most recently added to the stack will be the first handed back from the collection.

I find that the easiest way to understand what is the stack and how it works is by visualizing a pile of pancakes on a plate one on top of the other:

Let’s just say, for argue’s sake that I eat pancakes. And let’s just say that if I was served a plate like this I would eat the pancakes one by one. I were to eat them as I said I would have to start with the top one, otherwise the entire pile will ruin and all of these beautiful diabetes-causing treats would become a diabetes-causing mess! What I mean is, that the last pancake put on top of the pile is the first one I’d have to eat and the same goes with stacks (no I did not start a data-structure diet where I only eat ints, I need my beef and veggies too!) the last item on the stack, aka the top of the stack will be the first to go.

The action of adding another item to the stack is called “push” and the action of taking out the top item from the stack is called “pop”. So adding more pancakes to the pile can be done with “push”ing pancakes to the plate, and eating the top one is done by “pop”ping the top one. pretty simple isn’t it?

On the previous post we’ve learned how a linked list is a series of nodes linked together and do a chain – we can use this type of structure to help build our stack. The stack would contain a linked list who’s head node pointed to the most recently added (top) item.

Let’s begin with creating a linked list:

Pushing to the list is basically just adding a new node to the beginning of the list. In order to do that we first need to create a new item, link the item to point to the head of our list and then set the head of the list to be our new item. This way, we will create a new head to the list with a new value and keep the rest of the list linked to it!

I am going to use a “pop” function and since we’re using C here, we’re gonna have to pass a pointer to the pointer variable (double pointer yayyy) so we could modify the pointer itself:

Using this function we can always add a new item to the stack. Now how about some popping???

Funny isn’t it?

In order to remove the last item and pop it from the stack we need to do exactly the opposite! I’ll explain; First we need to take the next item that the head is pointing to and save it, then “free” the head item and then all that’s left is to set the head to be the next item we’ve stored on the side.

That’s pretty much it.

But why was I using a linked list and not an array for instance?

The main advantage a linked list has over an array is that it has no size limit and on modern days computers we can add billions and trillions of nodes without having to think about size and memory consumption (ALWAYS THINK ABOUT MEMORY CONSUMPTION NO MATTER WHAT YOU DO!). Also, it’s a very straight forward way to implement a stack – an array for example would require bounds checking to make sure that a “push” didn’t cause the item to exceed the array’s bounds. However, there are some downsides to this approach, and many of them has to do with performance and scalability; like whenever a new item is being pushed to the stack, a memory allocation occurs every time. This can end up causing undesirable performance characteristics in high performance systems.

Ar3p0

## Algorithms & Data Structures Day #1

Any of you who ever wish to succeed a job interview for any tech position (mainly developer and security researcher positions though) MUST master the art of algorithms and data structures. Actually, it’s a very important skill to have if you want to get serious with understanding computer programs for any reason and not just for the sake of finding a job.

So I’ve decided to share with you a quick 10 days walk-through into the world of algorithms and data structures – what do they mean, when to use what and how to implement them in the C programming language (I might add some x86 later on).

First we’ll start with two important definitions with the generosity of Wikipedia:

Data Structure-

a particular way of organizing data in a computer so that it can be used efficiently.

Algorithm-

a self-contained sequence of actions to be performed. Algorithms perform calculation, data processing, and/or automated reasoning tasks.

Now that we know what algorithms and data structures basically are, we can go on and start exploring the various common algorithms out there.

In computer science, a linked list is a linear collection of data elements, called nodes, each pointing to the next node by means of a pointer. It is a data structure consisting of a group of nodes which together represent a sequence.

In order to create and explain a linked list we first need to define a node – the most basic building block for many common data structures.  The node has two main functions;

1. Provides a mechanism to hold a piece of data.
2. Provides a mean to connect itself to other nodes and thus form a “chain”.

The node allows connecting itself to other nodes using an object reference pointer (the “next” pointer) that points at the address of the next node.

Let’s say we have a first node holding the integer value of 5 and a second node holding the integer value of 6. The first node’s object reference pointer will point on the second node and will form a chain:

We can keep adding more and more nodes to the chain using this process till the last member of the list that will contain an integer (in this case) and instead of an object reference pointer that points on the next node it will contain “null”.

Now we know how does a link list basically looks like but how can we implement it in code?

First we’re gonna need to define a struct in a recursive manner:

Now we can use the nodes! Hooray! Let’s create a variable to point at the first member of our linked list and call it samson (just because I can!):

It is good practice to check whether malloc returned NULL or not, do it every time you use it! Adding items to the list is super easy and can be done by allocating memory for the second node and just keep advancing to the next pointer!

Isn’t linking nodes fun? NOT REALLY! But it’s a must 🙂

As we’ve seen in the example, linked lists are sets of dynamically allocated nodes and as such they have very nice advantages over arrays for example. Items can be added or removed from the middle of the list and there is no need to define an initial size. However there are some drawbacks  – dynamic allocation for instance is a good place for bugs since pointers are used and the code gets much more complicated which might increase the risk of memory leaks and segmentation faults. Another drawback regarding dynamic memory allocation is that this action is less efficient in memory and the nodes are larger than array members since they hold both the value and another pointer. Oh and searching through a linked list is hell since there is no random access. For instance, if you want to find the N member of the list, you must iterate through the entire list till you find it, and with a simple “printList” function I’ll demonstrate how the iteration is done:

As you can see, I used a “curr” pointer to keep track of the node currently being printed. After printing out the value of the current node we set curr to point to the next member of the list till we reach the last one which is being recognized with “NULL”.

Adding items to the end of the list is very easy. we use the same logic we used in the previous example to iterate through the list but when we get to the end of the list using the NULL identifier, we then set it to point to another item!

Removing the last item of the list is quite tricky, since there are more things we need to do, like checking if the list contains only one member or more first:

“Wait a minute!!! You told us all about adding and removing items from the end of the list! what is I want to add or remove from the beginning of the list or from a specific location in the list???”

And you’re right! Unfortunately I am not going to explain how it is done just yet, we will talk about it tomorrow though, when I’ll explain all about the stack – how items are pushed to and popped from it and how this LIFO (Last In First Out) thing can be implemented in linked lists.

I am in a cheerful kind of mood though so I will tell you briefly how one can remove a specific item from the list.

I’m pretty sure you get the idea of dealing with linked lists, so you shall understand perfectly fine the following steps:

1. Iterate through the list till you reach the node before the one you wish to remove.
2. Save the soon-to-be-deleted node in a temporary pointer.
3. Set the previous node’s “next” pointer to point to the node after the node-to-be-deleted (in that way we’re skipping the deleted node).
4. Delete the node using the temporary pointer.
5. Free the memory for the temporary pointer.

(I know, I didn’t check for the case n=0, it requires the use of a pop() function which will be explained tomorrow)

And now a little bit of extra!:

What we’ve seen today is called a “singly linked list” since each node is linked directly to only one other node which works great when you only need forward access to the node. Sometimes you might want to be able to enumerate both forward and backwards and in these cases you will use a little something called a “doubly linked list“.

In a doubly linked list, each member points not only to the next member of the list but also the previews member, and as you’ve guessed this is being done by adding another pointer to the node_t struct.

Now that you get the logic, you know how to implement it using C code. 🙂

Good luck!

Ar3p0

## Ke\$ha to the hackathon!

” Wake up in the morning
feeling like p-diddy
grab my glasses
I’m out the door
I’m gonna hit the city
before I leave brush my teeth with a bottle of jack
’cause when I leave for the night I ain’t coming back “

Yeah I know, this isn’t really a politzer winning poem, or a healthy style of living,
It is however a lot like how a computer think!

A computer program usually comes to solve some sort of problem or simulate a situation.
In order to do that, one has to break down the tasks to perform into basic instructions so that the computer won’t miss any detail, and that my friends – requires some planning.

Imagine you’re to build a house. If you won’t use a well planned architecture you’ll probably
have a lot of issues building that house. The foundations have to be strong, the walls straight and the roof has to be 100% water proof for example.
It’s the same with computers.

A programmer has to follow a few steps before even writing th first line of code:
#define the_problem
#define tools_targets_backupPlan
break (easy_problems(hard_problems));
//and figure out the sequence of events!
/*Probably some I/O operations as well but we’re not gonna be talking

Those of you who noticed I used a bit of C/C++ syntax there – well done! Though it’s just cosmetics within the scope of this post.

So I believe with just a little effort even Ke\$ha can become a programmer. Actually, let’s have a bit of fun and show Ke\$ha how exactly we can turn the “tik tok” lyrics into a computer program flow if we only change the order of the lines a bit:

I know I know, It’s not exactly intuitive, oh you didn’t care about that and thought I don’t have a life?  Rude. True, but rude!

Seriously though, you should really follow these guidelines if you wish to write code that works and runs without any unexpected behaviors (more on that later) every time you run it! I know enough programmers (or hacker wannabes) who don’t go through this procedure when designing their code and let me tell you this – it shows. The outcomes are just not good; programs crush, causing memory leaks and even crushing the system and expose the computer to security breaches (don’t worry we’ll get there).

DON’T BE LAZY! Walk the extra mile! That’s what differentiate between the mediocre and the expert.
Also, don’t think you’re super smart and talented you can jump straight to writing code – always plan ahead, even if it’s just a simple recursive file infecting virus program (academic, naturally).

I’m off to do something useful with my life.
Nope, probably not,
Ar3p0

## It was a lover and his lass

With a hey and a ho and a hey nonino!

Sorry It’s been awhile since my last post, to be honest I thought I could just learn some C++ syntax and just code code code till my brain explodes or till I master the craft- Whichever comes first!

But unfortunately (or is it?) this programming language is big, wide and super complex and even a mini mastermind like mine would rather take the time and build a solid base before I jump to the cold water with the sharks and the bad-ass algorithms (why do shark like cold water!?!?).

In the meanwhile, I am also looking to solve some hacker-puzzles and brain training exercises so if any of my readers (yeah even you who accidentally got here) have any idea on such a site for the absolute beginner (not Trump level though, not that dumb after all) – please don’t be a stranger and help a guy out!

For now it is practice practice practice! Hope I’ll have some more interesting input next week and I could finally tell you all about the binary-auditing training package!

Till then my friends!

May the objdump be with you!

Ar3p0

## A new dawn – an old OS

So on the previous post I promised I would give some background on reverse engineering so here it comes –

##### Reverse engineering, also called back engineering, is the processes of extracting knowledge or design information from anything man-made and re-producing it or re-producing anything based on the extracted information. The process often involves disassembling something (a mechanical device, electronic component, computer program, or biological, chemical, or organic matter) and analyzing its components and workings in detail. – Wikipedia

Software reverse engineering is the art (yes, ART!) of disassembling a program of any sort (game, utility, OS, malware etc) in order to gain a deep understanding of what it does, it’s architecture and design so the reverser (the reverse engineer, from now and on -the reverser) could recreate the source code, manipulate the software to his needs and wills and research for vulnerabilities within the target program.

Today, software engineers of any background, avoid developing software using technologies that are easy for the machine to understand and use a “high-level” programming (and scripting) languages. I’ll explain:

The more the language is close to human language, the more stages the code has to pass in order to become a machine-readable language aka “assembly instructions” or machine code. It’s a bit more complicated than that and there are entire courses about this matter in universities (for those of you who want to get a deeper understanding I recommend on reading about software compilation and interpretation in high level and low level programming languages) but for us this would do for now.

Since programmers of today mainly use high-level languages (Java, C# etc) and scripting languages (python, js, php etc) and though it has it’s benefits (which are beyond the scope of this post, most of the programmers are just dumb and lazy),  most of them lack the knowledge on how the easy-to-read code becomes machine instructions, how the computer executes these instructions and how everything works beneath the surface basically (that’s the dumb and lazy part).

This is where hackers join in.

With a deep understanding of code compilation, CPU functionality and memory management, a hacker can gain a full access to a machine, exploiting vulnerabilities in all stages of compilation and interpretation and interfere with software’s execution.

Reverse engineering skills are very important for hackers and security researchers (the “good” hackers) since vulnerabilities aren’t always so transparent, one has to look behind the scenes in order to find them! And not all vulnerabilities are exploitable or worth exploiting.. more on that later.

So after this long introduction on reverse engineering I assume you understand why I am interested in becoming a reverser. But how can one become a reverser you ask?

A reverse engineer has to know the ins and outs of software, therefore one has to practice “low level” programming languages. I’ll focus on intel x86 assembler (32 bit) architecture since it is easier to understand and is much more “academic” than its successor the x64 architecture. But before that I will practice some C/C++ which are high level languages (since it is more human readable than machine readable haha) since these languages are the base of all software. Operating systems cores are developed mainly in C and some assembly and C++ for example.

I do not have to be a brilliant coder (that is not ma’ job!) but I do need some programming abilities to understand the goings of the software I wish to reverse. Does it make sense? no? deal with it.

I advised my mentor, Cru5d3r and he suggested the following:

• Learn to code
• Practice
• Understand you have no clue what you’re doing
• Go back to square one

The binary-auditor suggested practicing C++ and Assembly x86 as I wrote in previous post.

I am not going to teach any of these languages here, if you find it disappointing – sorry I’m not sorry. I will however share with you the exercises I’ll do (from the binary-auditing kit, duh!) and walk you through them.

But first things first.

Set up a Windows 7 (32 bit) workstation, it is recommended to use a VM (virtual machine) since we will run malware there eventually, and quite honestly – who the hell wants to use win (any version) on the host anyway!?

I like Oracle’s VM VirtualBox but you may use whatever you like.

After done installing the OS we’re gonna have to install some utilities such as google chrome (not gonna use IE whatsoever) and IDA Pro. The binary-auditor was kind to include a free version of IDA in the kit but you can get a better one if you know where to look or willing to spend some money.

Then we’re gonna need an IDE (Integrated Development Environment). This doesn’t have to be installed on the VM, not for now at least since we’re gonna need it mainly for practicing C/C++ and not for the “real thing” – I have it installed on the host computer. Binary-auditor recommends using code::blocks, I do too. It’s easy to use, very practical and it is cross-platform (to some extent). Make sure you set code::blocks to use the right compiler or you won’t be able to execute the programs you write on the host (ELF on linux and EXE on win are two different executable file formats).

For assembly we will need some other software but we’ll get to it.

I have downloaded an app to my mobile, called Learn C++ by solo learn and I also work with several books and tutorials. If this is going to be your first programming language I suggest you get someone to teach you in like a course or something, I do not recommend starting to learn coding from books, tutorials, youtube vids or even lynda. It will just mess you up. Luckily enough this isn’t my first language so for me it’s ok to use the free resources lol!

That’s it for now!

On the next post we will get our hands dirty – I will demonstrate and walk you through the first real C++ exercise! How exciting is that??? What? No? Fuck off.

Ar3p0

## Blog

“And on the third day, God created the Remington bolt-action rifle, so that Man could fight the dinosaurs. And the homosexuals.”

Hello everyone, I am ar3p0, a 16yo cyber geek from IL.

Now that we’re done with introductions it’s time to start talking process. No, not computer processes (well not just yet) but the process of learning! Isn’t it fun? no not really but this is my blog so I make the rules.

I have a basic background in C and OSs (especially linux since I have no friends) and some x86 skills. I tried to learn by myself and become a super-mega-l33t h4x0r (jk) using books, blogs, YouTube – u name it, and though I gained a lot of knowledge I still lack the practical experience, so after a year (or more) break I decided to clean the dust off my laptop (wasn’t that dusty, I do watch porn after all) and start looking for a better path for me.

I came across this site called binary-auditing where a university professor (don’t know who’s the man and where does he teach, it doesn’t say) published a complete guide for the absolute beginners. This guide is forcing you to take a practical approach and get your hands dirty so results are guaranteed for the ones who follow his instructions.

The guide opens with exercises in C++ and in x86 Assembly language, however it does not give you the information needed to complete the exercises so off to a C++ learning website/book whatever gets you going and then it is possible to keep enjoying the guide. The instructor, calling himself “binary-auditor”, does say it is not a requirement to be a C++ nor x86 Assembly expert but some knowledge in these languages could get you very far in the world of reverse engineering; So this time I’m gonna be a good boy and follow the instructions provided by the expert and who knows, maybe someday I’ll be one myself!

On the next post you should expect the following topics:

• What is reverse engineering and why do I find it interesting?
• Getting started with C++!

till then,

Ar3p0