Evolutionary Algorithms and Genetic Programming [1]

Introduction

Evolution in general means change and adaptation to the changes by a population and not individuals, changes that are passed on to the next generations. The idea of applying the biological principle of natural evolution to artificial systems, introduced more than three decades ago, has seen impressive growth in the past few years. Usually grouped under the term evolutionary algorithms or evolutionary computation, we find the domains of genetic algorithms, evolution strategies, evolutionary programming, and genetic programming.
Evolutionary algorithms (EAs) are ubiquitous nowadays, having been successfully applied to numerous problems from different domains including optimization, automatic programming, machine learning, economics, operations research, ecology, studies of evolution and learning, and social systems. In this article, we consider genetic algorithms in general and genetic programming to be specific.

Evolutionary Algorithms

Evolutionary algorithm is an overall term used to describe computer-based problem solving systems that use computational models of some of the known mechanisms of evolution as key elements in their design and implementation.

A variety of evolutionary algorithms have been proposed. The major ones are: genetic algorithms, evolutionary programming, evolution strategies, classifier systems and genetic programming. They all share a common conceptual base of simulating the evolution of individual structures via processes of selection, mutation, and reproduction. The topic of discussion in this article concerns genetic programming, but to understand genetic programming it is necessary to first understand the basic concepts of evolutionary algorithms.

EAs maintain a population of structures that evolve according to rules of selection and other operators that are referred to as genetic operators, such as recombination and mutation. Each individual in the population is measured for its fitness in the environment. Reproduction focuses on high fitness individuals and recombination and mutation agitate those individuals, providing general heuristics for exploration.

To understand EAs, it is necessary to have some appreciation of the biological processes on which they are based. In nature, the encoding for genetic information (genome) admits asexual reproduction. Asexual reproduction typically results in offspring that are genetically identical to the parent. (large numbers of organisms reproduce asexually; this includes most bacteria which some biologists hold to be the most successful species known.) Sexual reproduction allows some shuffling of chromosomes, producing offspring that contain a combination of information from each parent.

At the molecular level what occurs (wild oversimplification alert!) is that a pair of almost identical chromosomes bump into one another, exchange chunks of genetic information and drift apart. This is the recombination operation, which is often referred to as crossover because of the way that biologists have observed strands of chromosomes crossing over during the exchange.

Recombination happens in an environment where the selection of who gets to mate is largely a function of the fitness of the individual, i.e. how good the individual is at competing in its environment. Some “luck” (random effect) is usually involved too.

Some EAs use a simple function of the fitness measure to select individuals (probabilistically) to undergo genetic operations such as crossover or asexual reproduction (the propagation of genetic material unaltered). This is fitness-proportionate selection. Other implementations use a model in which certain randomly selected individuals in a subgroup compete and the fittest is selected. This is called tournament selection and is the form of selection we see in nature when stags rut to vie for the privilege of mating with a herd of hinds. Much EA research has assumed that the two processes that most contribute to evolution are crossover and fitness based selection/reproduction.

Evolution, by definition, absolutely requires diversity in order to work. In nature, an important source of diversity is mutation. In an EA, a large amount of diversity is usually introduced at the start of the algorithm, by randomizing the genes in the population. The importance of mutation, which introduces further diversity while the algorithm is running, therefore continues to be a matter of debate. Some refer to it as a background operator, simply replacing some of the original diversity that may have been lost, while others view it as playing the dominant role in the evolutionary process.

It cannot be stressed too strongly that an evolutionary algorithm (as a simulation of a genetic process) is not a random search for a solution to a problem (highly fit individual). EAs use stochastic processes, but the result is distinctly non-random (better than random).

Algorithm EA is

// start with an initial time
t := 0;

// initialize a usually random population of individuals
initpopulation P (t);

// evaluate fitness of all initial individuals in population
evaluate P (t);

// test for termination criterion (time, fitness, etc.)
while not done do

// increase the time counter
t := t + 1;

// select sub-population for offspring production
P' := selectparents P (t);

// recombine the "genes" of selected parents
recombine P' (t);

// perturb the mated population stochastically
mutate P' (t);

// evaluate its new fitness
evaluate P' (t);

// select the survivors from actual fitness
P := survive P,P' (t);
od
end EA.
Advertisements

Using YAML to transport data in ActionWebService

Here’s a handy tip for ActionWebService. Sometimes it could be a bit tedious to create the correct SOAP or XML messages to pass back and forth the webservices. If you’re using a Ruby 3rd party client (or even another Rails app as a client) you might want to try out YAML. It’s not entirely conventional but it works like a breeze and it sure beats the hell out of all that XML tagging.

Here’s the code to zip it up to as a YAML object:

yaml_obj = YAML::dump(your_object)

Even quicker — you can use a Hash and stuff everything inside the Hash. Then at the other end:

original_obj = YAML::load(yaml_obj)

There’s YAML for Java, Python, Perl and even Javascript. Check it out here

Don’t come after me if something doesn’t work though — it’s quite experimental at this moment, but it’s a pretty neat alternative to XML tagging.

[The Lands] – Tidings of War

Wilhelm crept up slowly to the small nook, as silent as any of his grandfather’s many spies. He was already familiar with the spot so the darkness posed no real problem – he just felt his way around until he reached the slight ledge which indicated that he should stop. He did just that, about twenty feet up above his grandfather’s Inner Court. It was a spot he came not infrequently, mostly just to daydream or to escape his all too boring court etiquette classes with Madame Voliante. Sometimes he just came to listen in to some of his grandfather’s conversations with his advisors. It was not really eavesdropping or anything. He decided that particular moral question a long time ago when he first discovered the small crack in the ceiling during his long and meandering wanderings in the ancient castle. His grandfather just happened to discuss Kingdom matters when he was up there, minding his own business really. Most of the things he heard were boring stuff like who did what and when and why it should be done. Sometimes though, more serious matters were discussed – some skirmishes with the Horde, some brilliant manoeuvres and not so brilliant routs, even some border disputes with Wranydis to the south. At times visiting dignitaries, usually royalty and sometimes merchants consulted with his father. The King even talked about his political strategies in his Inner Court though it was never the same with two different advisors. Wilhelm was intelligent enough a boy to realise some very interesting things were happening during those times.

The King was not a particularly physical person, tending towards the rotund in his old age. His four strapping sons sufficed in being physical, ranging from tall and commanding to simply large and burly. His red face, snowy white hair and long majestic beard in fact gave him the appearance of a kindly old man, not too bright perhaps, but rather a symbolic icon of monarchy in the kingdom of Liemia. Most of his subjects believed the real power behind the throne lie with his eldest son Johann, the Prince Regent and heir apparent. In fact none except his sons knew otherwise. Wilhelm, rich with knowledge from his hidey-hole knew only too well about his grandfather’s sharp mind and cunning plots.

Orphaned at the age of two when the first wave of the Horde massacred the previous border town of Kordelus, he had since stayed in the ancient seat of Liemian power, the Casa del Liem. His father was the Duke of Kordel, his mother the youngest daughter of the King of Liemia. Not a single soul survived the ravaging of the duchy of Kordelus. It was very fortunate that Wilhelm was spending the summer with his grandfather at the Casa del Liem when the the Horde swept through the eastern borders and obliterated more than fifty villages and towns in three kingdoms. They were not merely conquered but totally massacred and uprooted. Entire towns and villages ravaged and depopulated. Any resistance was swept away with brutal efficiency – no captives were ever kept beyond a few days. the Horde ate what they could, including humans. Those whom they could not eat, they decapitated and their heads piled up in the centre of the town. Fields bearing the rich loa grains Kordelus was famous for were burnt to the ground, the careful irrigation making it possible to grow loa grains savagely destroyed and whole rivers dammed and diverted just to flood over the crops. The horrors of the invasion were so great that the lands the the Horde so barbarously decimated were still left barren after all these years.

The bloodied Horde was finally met with the combined forces of the Federated Five Kingdoms on the plains of Suondy. The titanic battle raged throughout the day and when it was done, less than a fifth of the fifty thousand brave men was left standing. The Horde however, was no more.
The terrible battle took an even worse toll on the survivors. Thousands of able-bodied men had been conscripted for the war and only the women, children and disabled were left to till the land and grow the crops. Whole counties and provinces were abandoned in flight as the horde approached. To those who returned, disease and starvation overtook them. Plagues wiped out entire villages and towns and the lack of food only bred the horrors of malnutrition and raised the even uglier spectre of crime. Widespread looting and robbing became common in those early years after the battle, groups of ragtag bandits taking over whole provinces even. However, order soon prevailed as the kingdoms recovered and after a couple of years of chaos and mayhem, matters returned to almost normality. All has been quiet and peaceful for five years now; even bandits were a rare sighting. This year however, the first sign of hostile orcish activity has been sighted since almost fourteen years ago.

Wil settled in nicely on his favourite spot. Something exciting was about to happen that day. All week long ambassadors, princes, dukes and all sorts of diplomats have invaded the capital city Rourin. The Council of the Lands, convened once every two years at different kingdoms and duchies have finally arrived after thirty years, once more to Liemia. For months now, his Uncles Johann and Rikard have busied themselves with the arrangements and accommodations for dignitaries from almost fifty recognised members of the Council. It all came down to today, the first day of the Council, which was to last until all matters have been discussed over a period of four weeks, after which the Council will be reconvened two years from now.

“Your Majesties and Your Highnesses,” declared a gaunt, bony man clothed in precise finery, “May I have your attention please.” He stepped briskly forward in stiff formal protocol then made a small well-defined bow. “May I present His Highness Prince Mattheus of Nalvia.”

Wil recognised him as Roderic Thaddieu, his grandfather’s High Chamberlain, meaning he gets announce the guests as they arrive, something that he does with a very irritatingly and pompous manner.

Prince Mattheus was a dark-haired young man, copper of skin and a cheerful smile on his face. Wil liked him at once, even though he had never actually seen him before. He knew though that Mattheus was the youngest son of the king and has a tainted reputation of being brash and immature. Nalvia was a neighbouring kingdom, smaller than Liemia by almost half, but she has one of the largest seaports and the largest fleet of warships among the Lands. She was also a member of the Federated Five Kingdoms that stemmed the tide of destruction brought by the invading hordes.

The other guests nodded or bowed in acknowledgement according to their station. A few frowned at him openly for being almost half an hour late, others just ignored him completely, something Wil knew as quite foolish. Being hostile or snubbing Nalvia or her representative was not a good idea, since the break-up of the Federated Five Kingdoms after Battle of Soundy. The Council is about the only thing she even considers to attend. They needed her fleet of fast and sleek warships because that is the only thing that the the Horde did not excel humans in. Somehow, the Horde disliked water and their ships were not very well built. In one of the decisive and dramatic battles before the Plains of Suondy, five of the swift Nalvanian warships darted in between the massive galleons the orc tend to build and crippled ten of them before the the Horde could react. Then the larger Nalvanian battleships swept in and crushed each and every one of them, losing only three ships compared to the twenty-over manned by the the Horde.

Roderic nodded perceptibly then announced in a grand manner, “The last representative of the Council of the Lands has arrived. The Council will proceed to convene.” A few of the representative coughed and one yawned. Roderic cleared his throat importantly and continued, “Presiding as host shall be King Boric del Liem of Liemia. Your Majesty?” With that, he bowed low and backed out of the room, closing the door behind him.
“Ah, yes,” nodded King Boric. “Ahem. Shall we begin now?”

“Your Majesty,” said a tall gangly man politely, rising to his feet. Wil recognised him as a Semprian and noted that he wore the customary gown of minor nobility and carried an ceremonial hriss, a wicked-looking hooked dagger. He concluded that the Semperian was an ambassador, most probably recently arrived. Not only he was wearing gold earrings on both ears and one in his nose but heavy looking gold chains with intricate designs hung over his neck. Any person wearing that amount of gold in Rourin will not survive more than a few hours in broad daylight and much less after dark.

“I be Illrendris sa Ragedren, on behalf of my lord of Rallaka-Iss,” he introduced himself and flicked his hriss casually. “We shall get to the point now, yes?” Without waiting for an answer, he continued.

“I see the Horde!” he spat to the ground. Wil’s grandfather winced noticeably, along with some of the other representative. “I see them everywhere! They be coming for our eyes up north, hundreds and ten hundreds of them. But strange, they not attacking, just looking.”

“Ahem,” said Wil’s grandfather slightly ruffled after the abrupt speech. “Yes, we were about to get to that. About – ”

“As what the Semperian put so succinctly,” interrupted a large middle-aged man, also ostentatiously clothed in fine Arian silk and wearing a ring of different stone in each of his ten fat fingers.

Wil sat up and stared at the fat man. Something about him told Wil that he was a dangerous man and should not be trifled with. He was not sure if anyone else noticed the way that the man moves. The arrangement of his rings, which could be interpreted as a crude display of wealth, was in the ready pattern of power. It could have been accidental. However, those small deft gestures he so casually and probably subconsciously performed were definitely a weaving and from the looks of it, a weaving of minor protection. Wil wondered whom he could be representing.

“We have Horde trouble at our doorsteps again, what can we do?” he said quite grimly. Some of the other Council members frowned at him and even in puzzlement. None of the others recognised him either. Prince Johann stepped forward from behind his father and said quietly, “Our guest is the representative from the Isle of Mullind, his Eminence Duke kil Roadac.”

There were loud murmurs in the Inner Court and Wil furrowed his forehead. Mullind is a small island off the southern shore, beyond even Nalvia. Her population consisted of mostly fishermen and sea harvesters. She had royalty of some sort a long time ago but the line had since died. She kept to herself mainly and did not have a voice in the Council even before the first orcish invasion. So what was a representative of Mullind doing in Liemia now and in the Council of the Lands of all places? Wil added another mystery to it himself – a skilled magic-weaver representing them? He suddenly felt very uncomfortable. Should the man from Mullind cast any weavings of detection, he would most definitely be found and that could be unpleasant.

Wil’s grandfather looked nonchalantly at the Council. Wil wondered what his plan was – it has been quite educational so far and he was very much eager to know what followed. Things were rarely this exciting. His cousins found him strange that he does not enjoy riding and swordplay as much he loved books and reading. Books and lessons by the royal tutors were a drag and only served to impede them from the real purpose of the day – sword fighting, archery or horse riding. The older cousins readily admit that books have their usage, though limited. Any serious reading if necessary can be acquired by using the services of a cleric or a monk. So when they realised Wil had a passion for books of any sort over the more physical aspects of growing up, they were quite mystified. He could not tell them the sweet thrill of the unknown, the mysteries that were locked behind the innocent seeming covers of a book and the excitement of gathering knowledge and applying them readily like what he was doing now.

By six, he could read and write, storing what became later his massive library of notes and books. It was really quite fortunate that he was a prince – otherwise he could have never afforded to even have the paper for his notes! Seeing his potential, his Uncle Johann hired the best tutors for him and by the time he was twelve, he could easily surpass most of them. The only thing that balked him so far was the firm belief of his grandfather that no true son of del Liem should be involved in the dark arts of magic weaving. Therefore he resorted to learning what weaving is instead of learning how to weave magic himself. The roundabout way did not exactly please his grandfather but he was not disobeying his grandfather’s wishes. What surprised him later was that not many sorcerers were not sure precisely what they were doing when they actually spin from the web of magic to form what they generally know as spells.

As a result of his dedication to the literary and subsequent neglect of other matters, Wil remained gangly, large boned and not much good in any physical sports, much to the regret of his Uncle Xavier. It was not that he was poor at swordplay or could not ride a horse – in fact he was reasonably good with a broadsword and had such instinctive skills that he nearly defeated cousin Nikolas, his Uncle Johann’s eldest son. Unfortunately he lacked the power, stamina and determination of a true swordsman. Once Nikolas knew his weakness, he merely wore Wil out and waited for an opening, both which came soon enough. It was not long before Wil was thoroughly beaten by almost every boy his age in swordplay.

“So what is our neighbour Mullind’s interest in the matters of the Lands?” asked the representative from Toumheilm boldly, clearly voicing the sentiments of the gathered Council. Mullind was never popular among the Council of the Lands, isolating herself from the mainland and keeping only minimal trading contacts. Most took offence to that, especially Nalvia who declared herself as having the greatest Fleet in the Lands but could not even land on Mullind. Some believed there were countless treasures in Mullind, selfishly hoarded by the Muls, others spoke of an island of horror and monstrous tyranny and yet others spoke of and island of powerful but mad magic-weavers. Folklore were rarely accurate, decided Wil.

“Our interest is the preservation of our lives and our land,” replied the fat man coolly, staring at his enquirer.

“So says you,” sneered the ambassador from Toumhielm. “We says you be traitorous scum ally with the filthy the Horde!”

Some of the Council backed away hurriedly. Wil gulped. No one has ever fought in the Inner Court before. Not since Ka’lent the Usurper murdered King Dekliem the Mad. Now it looked like someone or more could be killed. Wil’s mind raced madly – this could be really bad. If the fat man kills the Toumite, which Wil had no doubt he could, Toumhielm might crush Mullind – Toumhielm is one of the largest Kingdoms in the and the second largest army. Not good.
Before Johann could step out again, the fat man scowled and said, “Peace! Are we to fight the Horde or among ourselves?”

“But first, we must be assured that you are not allied with the Horde against us,” quickly answered a gaunt old man whose hair was almost all white. Wil recognised him as the Prince of Moroug, Treldin ran Holdiem, a distant cousin of the del Liems. He is a well-known figure of authority among the northern kingdoms and many of them look toward him for advice. As a result Wil knew Treldin has the backing of the powerful mining kingdoms of the Northern Reaches even though Moroug herself is but a small mountain kingdom. A good ally to have.

“I can furbish no further evidence than this – the Horde have been observed by the Lords of Mullind to possess skill of magic weaving equal that of any among us, including those who dwell in Mullind. Without us, you have not the power to stop them if they employ the arts.”

There was a small shocked silence. Then almost everyone started to speak at the same time. No, it could not possibly be! How could such they know of such? The Mul is over exaggerating their powers. The Mul is in league with them! But yet … Even the rash Toumite hesitated. The Horde were uncouth savages and possesses only brute strength and a mad will to destroy. But magic-weaving? It was arrogance on the part of humans and Wil regretted to realise that he had felt the same way about the the Horde too. Borick lifted his hand in a plea for silence and only when Treldin spoke did most of the Council listened again.

“What sort of magic do they possess?” asked Treldin finally.

Some of the faces in the Council were blank. To them, magic is magic, woven by the practitioners of the dark arts. Wil understood what he meant though, as with his grandfather and Uncle Johann, both who seem to fade into the background. Wil kept a sharp eye on both of them. Wil almost automatically recalled his lessons on magic. There is basically two major variations of magic. Essentially, all magic flowed from the same source, the power of existence. He remembered from his notes on the subject – every single object contains certain innate raw power of its own, it is the power which keeps it in existence. This power can be drawn out by careful weaving and repositioning of the powers surrounding it, always careful to retain an overall balance. This is what magic-weavers do. Priests and other holy men derive their power from their gods by praying for them.

“This is sacrilegious!” sputtered a middle-aged man, who Wil know as The Archbishop of Mendachia. Mendachia is one of the few free city-states in the Lands, free only because of its enormous influence as the holy city of Mendach, father of gods. “Are we to listen to these godless men? The Almighty will surely protect us from the monsters!”

Some of the Council members looked uneasy while the kil Roadac completely ignored the interruption. Most religious men believe that only the gods has the right to grant powers of magic and the lay magic-weavers were godless heretics. “Very strange weavings – the likes which was never seen before. Their weavings seem extremely intricate and powerful. We are still investigating it.”

“King Borick,” demanded the Archbishop. “Are we to listen to any more of this heretical drivel? Should you not impose the will of Thiara, your patron goddess and wife of Mendach to lead them away from sin?”

Wil could understand his indignance. From what he read (many of the books that he learnt from were banned in most kingdoms, including Liemia) the gods were another source of the power of existence. He was shocked initially and still remained somewhat uncertain, having being brought up quite religiously to worship Thiara. However, the book he read described the gods as highly concentrated sinkholes of power. To enable miracles as performed by priests like the archbishop, the god has to yield a part of his power, essentially his very being. In return, he demands prayers, which will be transformed by the power of faith into the power of existence, which in turn can be released to their faithful, the cycle going on and on eternally. The book was quite thick and had no pictures. Wil read it from cover to cover ten times before grasping what the author meant to say. Somehow Wil struggled to agree with the author, who was quite anonymous. Putting his name on the book would of course be like signing his own death warrant.

Wil’s grandfather replied mildly, “The matters of the Council are worldly, my dear brother. Let us hear them out fully before exacting penance.”

Liemia’s patron goddess was Thiara, wife of Mendach and the King was nominally the High Priest of Liemia as well. Wil admired his grandfather and his choice of reply. He just reminded the Archbishop of his spiritual authority, asking him subtly to relinquish his authority to himself and allow him to make judgement. The Archbishop has no choice but to accede, since the Council is held in Liemia and the highest spiritual authority in Liemia was none other than the King. The Archbishop nodded grudgingly and the rest of the more religious members of the Council seem appeased for the moment.

“It is apparent that they stole the secrets of Arachdes from us,” claimed the representative from Brunnel, a large golden-haired man, glaring at kil Roadac. “The thieving demons!”

“Or perhaps the Muls sold it to them,” sneered a shorter bulkier man by his side.

Treldin’s face hardened.

“That is a possibility, who are we to say not that you taught them the dark arts,” said Treldin. “They surpassing you and now you are seeking our help to destroy all evidence of your treachery!”

“Preposterous!” exploded kil Roadac, his face reddening. “What is wrong with you people? Can you not see beyond your miserable squabbling that we face a foe more deadly than we did fourteen years ago?”

Traitor scum Horde-lover!” spat the hot-tempered Toumite ambassador. “We destroyed them once, we destroy them again!” He half drew his sabre out of his scabbard. The Archbishop stepped back, hands swiftly drawing a circle. A circle of protection, noted Wil critically. Very well practised, very well formed. The Brunnelian ambassador and his friend went straight for their daggers while the Semperian has already flashed his hriss out. Maybe it was not that ceremonial after all.

“You fools!” raged kil Roadac. “You – ”

“Peace,” interrupted King Borick gently, his voice a calming contrast with the fuming Mul. “We are here to talk, not fight.”

Kil Roadac sat back heavily on his seat and Treldin held the Toumite with a restraining grip. The others, realising their awkward display has broken all protocols by going for their weapons in the Inner Court, sheathed their weapons. Everyone also noticed that Prince Johann and the King were not armed at all.

The Semperian bowed low and said, “Apologies, King Borick, one gets the temper not befitting. Begs for forgiveness now.”

“Don’t worry,” assured the King gently. “We are all uncertain and uneasy about these new happenings. I too have an announcement to make.” He paused for a moment, they surveyed the room in practised hesitation. “We have also sighted the Horde and we have fought them.”
Silence.

“What!” the Toumite shouted and drew his sabre in a sweeping arc and brandishing it before him.

“Put that thing down, Joraqk!” commanded Treldin sharply. “You are not going to fight any the Horde in Borick’s court!”

Looking rather foolish, Joraqk sheathed his weapon.

“Thank you, Treldin,” said Borick. Treldin nodded curtly. He does not really like surprises and there were one too many surprises already.
“What do you mean, you have fought the the Horde?” demanded kil Roadac. “Where did you do that and why were we not informed earlier?”

Borick sighed softly. For all Wil knew, it was a true expression of sadness? Resignation?

“Please understand what we have gone through.”

Borick signaled to Johann and with a slight nod, he walked quickly out of the room.

“My eldest son will bring in one of the the Horde we have captured. Let me explain what had happened and let you be the judge of it right here in my court.”

Wil sat terrified up in his hole. What is going on? How did he manage to miss it all? He accused himself mercilessly. He should have caught on to the signs – all that secrecy before the Council. He has thought it was because of the Council itself which was the commotion but never did he imagine -. He was going to meet, for the first time in his life, the creatures that killed his parents and ravaged his birthright. He trembled in fear and anticipation, heart beating so loudly he was positive they could hear him from below. Do I feel anger? he wondered to himself. Should I? All his life, Wil had imagined what he would do if he faces a creature from the Horde. Kill it! Torture it! Make it pay for what it did! Holding on to his breath, he stared below.

[Securing Internet Banking] Part 5 – Trojan Attacks

In Greek mythology, the Greeks tricked the Trojans into believing they have won the war building a large wooden horse outside the city and hiding in it. When the Trojan soldiers celebrated their victory by carrying the horse into city, the Greeks launched a surprise attack from within the city and destroyed Troy. Trojan attacks on computer systems are based loosely on the same principles and often just as deadly.

The Trojan can be in any form – executable application code, music files, documents, emails or even images, with the sole purpose of getting the unsuspecting bank customer to install or execute or view it on his personal computer. Trojan attacks can be directly obvious, for example, attachments in emails that promise something ‘exciting’ found in the file (usually with pornographic connotations). The file attachments can be executable applications or common file formats such as Word or Excel, MP3 audio files or even JPG images[1]. Another common way for Trojans to gain entry is to pretend to be useful software (including shareware, open source software and even normal commercial software that come in CDs) or plug-ins or file viewers. Any method that can propagate viruses can also be used to propagate a Trojan in the system. The Trojan can even start its life as a worm or a virus and replicates itself throughout a network, so the entry point might not obvious.

As Trojans are only the carriers, the real harm is usually done by the Trojan’s payload. Common Trojan payloads include viruses, worms, rootkits, keyloggers and screenloggers. Trojans are a generic tool used by hackers to penetrate computer systems, and their intent varies in the payload that comes with the Trojan. The earlier Trojans were mostly used to propagate viruses that cause immediate damage (by deleting files or defacing web sites or launching denial-of-service attacks) but these have eventually moved on to more insidious theft-based eavesdropping attacks that cause financial damage. While virus-based Trojans are usually generic and widespread with the intention of spreading to as many systems as possible, eavesdropping Trojans are usually more specific. In a recent case in Israel, a married couple was arrested for corporate espionage using Trojans[2]. Such Trojans are harder to detect as they are geared towards a specific environment and cannot be normally detected by anti-virus or anti-spyware applications.

Eavesdropping Trojans are usually offline attacks – the Trojan will capture information on the computer and stores or sends it for later usage by the hacker. For Internet banking systems, eavesdropping Trojans are an obvious threat to the bank customer’s personal computers as they compromise the integrity of the communications between the Internet banking system and the bank customer. According to the Anti-Phishing Working Group (APWG), there were 180 unique phishing-based Trojans (keyloggers) and 1912 websites spreading password-stealing Trojans detected and recorded by APWG researchers in December 2005 alone[3]. A report released by Counterpane Internet Security and MessageLabs in March 2006 found that financial services and banking industry organizations suffered the largest percentage of Trojan attacks in 2005 with close to 40 percent of all Trojans focussed on them[4].

Keyloggers are a common payload in Trojan. Keyloggers monitor the keys that are pressed at the breached computer. They are typically used to trap data that is keyed in at the computer and to relay the information to the hacker. Many keyloggers use a feature in Microsoft’s Internet Explorer called Browser Helper Object (BHO) to detect the sites that are visited in order to collect the needed set of data. Keyloggers, like remote monitoring software, are not inherently malicious. In fact, many keyloggers are sold as commercial software for legitimate purposes such as monitoring and controlling a network of personal computers within a corporate environment. For example, it is ironic that the software ‘Perfect Keylogger’ used by the teenage hacker in Singapore described below is software that is sold commercially for security purposes[5]. Screenloggers are a variant of keyloggers that capture the screen as well as the keystrokes, and is basically used to overcome counter-keylogging measures that display on-screen security features.

A rootkit is a set of software tools used by intruders to conceal their activities after the computer has been compromised. Rootkits helps the intruders to maintain their access to the system without the owner’s knowledge. Trojans that install rootkits often install other payloads and uses rootkits to prevent detection. Rootkits are also often used in the creation of botnets or zombie networks of computers captured by hackers. Such botnets are often used in launching other attacks such as phishing or sending out spam mails.

A recent infamous Trojan is the Sony rootkit controversy[6]. A piece of software called Extended Copy Protection (XCP) used for copyright protection and digital rights management in audio CDs was used on some audio CDs that were distributed by Sony BMG. In this case, if a user attempts to play the music on a Windows system, XCP will be installed in the computer without knowledge or permission from the user. It will then remain resident in the user’s system, intercepting all accesses of the CD drive to prevent any other media player or ripper software other than the one included with CD from accessing the music tracks of the Sony CD. More ominously it also alters the operating system registry settings which render the CD drive inoperable if any attempts are made to remove the software. While the controversy drags to messy legal disputes, it is worth noting that Trojans do not necessarily come from hackers across the Internet. If instead of DRM software an audio (or video) CD or DVD installs other malicious software such as keyloggers or screenloggers, the entire system can be compromised. It does not take large leaps of creativity to imagine some teenager or child popping in a nice looking CD he gets from a schoolmate into the family personal computer leading to identity theft and security breaches.

Another trick used by Trojans work more insidiously. When a user clicks on a hyperlink to an Internet website or types in the URL to the site, the web browser requests the operating system for a translation of the URL to a set of numeric IP addresses that are the ‘real’ addresses used by the network to find the correct server. The operating system would first go to a local hosts file to check if a local translation is available. If it is not, (and that is usually case unless the website is a part of the Intranet), it will reach out for the nearest Domain Name Server to request for a translation. Some Trojans modify the local hosts file to add in redirection to a phishing site. For example, if the bank customer types http://www.citibank.com and the hosts file has been ‘poisoned’ to redirect to a phishing site, the bank customer will not be able to tell that it is not the correct web site. With a simple command to remove itself after the attack, this attack is almost invisible. When paired with an efficient phishing site, these hosts file poisoning attacks are extremely dangerous.

Trojans are so common that it has even been offered as packaged software. Researchers from PandaLabs found a system that offers a custom-made Trojan for sale[7]. For only US$990, the system offers a personalized Trojan, complete with tech support. If the file is discovered the designer provides a guarantee to alter it so that it may continue to avoid detection from updated antivirus software.

Another sobering fact is that Trojans are not only installed from malicious websites but are often injected by friends or someone the user knows and normally trusts. In a recent case in Singapore[8], a teenager invited some friends via email to play some computer games that embedded a keylogger. Using this Trojan the teenager managed to acquire the Internet banking user names and passwords from his friends and successfully paid his phone bills using his friend’s account.

[1] See Declan McCullagh, Robert Lemos, Trojan horse exploits image flaw (September 2004) at http://news.com.com/Trojan+horse+exploits+image+flaw/2100-7355_3-5385995.html

[2] http://news.yahoo.com/s/nf/20060308/tc_nf/41980

[3] See Phishing Attack Trends Report – December 2005 at http://antiphishing.org/reports/apwg_report_DEC2005_FINAL.pdf

[4] http://www.counterpane.com/pr-20060313.html

[5] http://www.blazingtools.com/bpk.html

[6] See Mark Russinovich, Sony, Rootkits and Digital Rights Management Gone Too Far (October 2005) at http://www.sysinternals.com/blog/2005/10/sony-rootkits-and-digital-rights.html

[7] See Peter Pollack, Malware moves up, goes commercial, Arstechnica (Feb 2006) at http://arstechnica.com/news.ars/post/20060225-6264.html

[8] http://tech.monstersandcritics.com/news/article_1077952.php