Ready Player One, by Ernest Cline

If you were born before the 80s, Ready Player One is going to fill you with melancholy. Ernest Cline combines several classical young adult themes - like a battle versus an oppressive corporate evil, true and pure love, villainy and lack of honor defeated through friendship and good feelings - with (often obscure) geek memes of the 70s and 80s. If you are the kind of person who likes to impress by quoting lines from movies or telling of your adventures in games that are older than your children, this is the book for you. OK, I won't be mean, the book is going to be fun no matter when you were born, but the level of enjoyment may vary.

However, the book is still a young adult book at its core and, besides the overall message that you actually have to make an effort to reach your goals - an often neglected tidbit in young adult books and movies - it reads like one. Young heroes, with enough skill to pass through the challenges of the story, but awkward enough to also be endearing, manage to save the world through the power of their dedication and ideals. Also Chekhov's Gun has been used so much that it left gaping holes in the story. Amazing how random things in the story come perfectly together at the end. Let a bitter Harry Potterish aftertaste.

But let's start with the plot, which is pretty fun. It all happens in a dystopian world where energy reserves dwindled, gasoline became way too scarce and expensive, Elon Musk never happened and most people live their lives in a virtual world called OASIS, created by a brilliant yet reclusive visionary who made sure the system will remain secure and anonymous. Kind of like the Internet, but without the MPAA or the NSA. Yeah, it already sounds like an impossible dream, doesn't it? Well, the maker of the game world dies and leaves his entire estate (hundreds of billions of dollars and complete control over OASIS) to whoever finds the Easter Egg he his inside the game. The heroes of the story are young "egg hunters", while the villains are corporate drones who have been hired to find the egg for their company.

The writing style irked me a little. I know it is Cline's first book, and it certainly was a decent effort, but it had that way of explaining things that I call "fake past" in which the narrator explains things as if he is telling a story from the past. "The OASIS was...". Since this is supposed to happen in the future, it took a while until I could stop feeling irritated by it. However this has the advantage of being very easy to read.

I think it matters a lot if the reader is into cultural references. I could understand some, I could remember some, most of the references in the book, though, were ancient or obscure enough that even I didn't recognize them, and I am a pretty geeky person. I felt rewarded when I could "get it" and frustrated when I didn't, so probably it will be the same for most readers. If you don't care about these things, I think it is better to wait for the movie.

...which is in the works, with Steven Spielberg attached to the project. It might be difficult to put the story on the screen, though, since the book made an effort to describe a future world where everybody is obsessed with this specific period of the late 20th century, kind of like the Star Trek episodes that happened in the past or that required Kirk or Picard to know some specific book from the school curriculum. There is even a Ready Player One web site, that might have some Easter eggs in it (they would be dumb not to program some) but to me it seems both way too geeky and way to social at the same time.

Bottom line: a fun book for geeks. I hope it inspires the younger generations to look at the world a little bit differently, but I don't have my hopes up. My guess is that they will go all 'Meh' on a story that references anything that happened last century.

Read More

T-SQL: Joining two very large tables (or not) when trying to determine the hierarchical relationship between the records

Update: after another very useful comment from NULLable, I tried several new ideas:

• range queries - trying to specify that the child StartIp, for example, is not only greater or equal to the parent StartIp, but also less or equal to the parent EndIp. In my case the query didn't go faster and adding new indexes as recommended in the comment made is slower. I believe it is because the range values are not static or just because clustering the start/end IP index is really way faster than any logical implementation of the search algorithm
• cursor hints - obviously a very important hint that I should add to almost any cursor is LOCAL. A GLOBAL cursor can be accessed from outside the stored procedure and weird things can happen when running the stored procedure twice at the same time. NULLable recommended also STATIC READ_ONLY and FORWARD_ONLY. In truth the performance of the query doesn't really depend on the speed of the cursor, anyway, but I found an article that discusses the various cursor hints and ends up recommending LOCAL FAST_FORWARD. Check it out, it is very informative. My tests showed no real difference in this particular scenario.
• RI-Tree implementation in SQL - the article that NULLable linked to is amazing! I just don't get it :) I will update this more when I gain more IQ points.

Update 2: I kind of understood the Relational Interval Tree implementation, but I couldn't find a way for it to help me. The code there creates a computed column of the same type as the IP columns then makes a BETWEEN comparison and/or a join or an apply with two table functions. I can't imagine how it could help me since the original query is basically just two BETWEEN conditions. But still a very interesting article.

I wanted to have a database of all Ripe records, in order to quickly determine the Internet Service Provider for an IP. We are discussing IPv4 only, so the structure of the table in the database looked like this:

CREATE TABLE [dbo].[RipeDb](
  [Id] [int] IDENTITY(1,1) NOT NULL,
  [StartIp] [bigint] NULL,
  [EndIp] [bigint] NULL,
  [NetName] [nvarchar](450) NULL,
  [StartTime] [datetime2](7) NULL,
  [EndTime] [datetime2](7) NULL,
  [ParentId] [int] NULL)

As you can see, I translate IPs into BIGINT so that I can quickly sort and select stuff. I also added a ParentId column that represents the parent ISP, as you have some huge chunk of IPs, split and sold to other ISPs, which in turn are selling bits of the IP range they own to others and so on. The data I receive, though, is a simple text file with no hierarchical relations.

The task, therefore, is to take a table like described above, with more than four million records, and for each of them find their parent, if any.

The simplest idea is to join the table with itself like this:

SELECT rp.Id as ParentId, 
   r.Id 
FROM   RipeDb r 
   INNER JOIN RipeDb rp 
       ON rp.StartIp <= r.StartIp 
          AND rp.EndIp >= r.EndIp 
          AND rp.EndIp - rp.StartIp > r.EndIp - r.StartIp 

This gets all ancestors for each record, so we need to use a RANK() OVER() in an inner select in order to select only the parent, but that's beyond the scope of the article.

Since we have conditions on the StartIp and EndIp columns, we need an index on them. But which?

Through trial and error, more than anything else, I realised that the best solution is a clustered index on StartIp,EndIp. That is why the first column (Id) is not marked as PRIMARY KEY in the definition of the table, because it has to look like this:

[Id] [int] PRIMARY KEY NONCLUSTERED IDENTITY(1,1) NOT NULL

. Yes, primary keys don't have to be clustered.

But now you hit the snag. The process is EXTREMELY slow. Basically on my computer this query would end in a few days (as opposed to twice as much with a nonclustered index). What the hell is going on?

I tried several things:

• JOIN hints (Merge, Loop and Hash joins) - the query optimizer seems to choose the best solution anyway
• Various index combinations - nothing beats a clustered index
• Taking a bunch of records and joining only them in a WHILE loop - it doesn't fill up the temp db, but it is just as slow, if not worse

At this point I kind of gave up. Days of work trying to figure out why this is going so slow reached a simple solution: 4 million records squared means 16 thousand billion comparisons. No matter how ingenious SQL would be, this will be slow. "But, Siderite, I have tables large like this and joining them is really fast!" you will say. True, with equality the joins are orders of magnitude faster. Probably there is either place for improvement in the way I used the indexes or in the way they are implemented. If you have any ideas, please let me know.

So did I solve the problem? Yes, of course, by not relying on an SQL join. Think about how the ranges are arranged. If we order the IP ranges on their start and end values, you get something like this:



For each range, the following is either a direct child or a sibling. I created a stored procedure that called itself recursively, which should have worked, but then it reached the maximum level of recursion in SQL (32 - a value that one cannot change!) and so I had to do everything myself. How? With a cursor. Here is the final code:

DECLARE @ParentIds TABLE (Id INT,StartIp BIGINT, EndIp BIGINT)
DECLARE @ParentId INT
DECLARE @Id INT
DECLARE @StartIp BIGINT
DECLARE @EndIp BIGINT
DECLARE @OldParentId INT

DECLARE @i INT=0
DECLARE @c INT

DECLARE curs CURSOR LOCAL FAST_FORWARD FOR
SELECT r.Id, r.StartIp, r.EndIp, r.ParentId
FROM RipeDb r
WHERE r.EndTime IS NULL
ORDER BY StartIp ASC, EndIp DESC

OPEN curs

FETCH NEXT FROM curs
INTO @Id, @StartIp, @EndIp, @OldParentId

WHILE @@FETCH_STATUS=0
BEGIN

    DELETE FROM @ParentIds WHERE EndIp<@StartIp

    SET @ParentId=NULL
    SELECT TOP 1 @ParentId=Id FROM @ParentIds 
    ORDER BY Id DESC

    SELECT @c=COUNT(1) FROM @ParentIds

    IF (@i % 1000=0)
    BEGIN

    PRINT CONVERT(NVARCHAR(100),SysUtcDatetime())+' Updated parent id for ' + CONVERT(NVARCHAR(100),@i) +' rows. ' + CONVERT(NVARCHAR(100),@c) +' parents in temp table.'
    RAISERROR ('', 0, 1) WITH NOWAIT

    END
    SET @i=@i+1

    IF (ISNULL(@OldParentId,-1) != ISNULL(@ParentId,-1))
    BEGIN
        UPDATE RipeDb SET ParentId=@ParentId WHERE Id=@Id
    END

    INSERT INTO @ParentIds VALUES(@Id,@StartIp,@EndIp)

    FETCH NEXT FROM curs
    INTO @Id, @StartIp, @EndIp
END

CLOSE curs
DEALLOCATE curs

I will follow the explanation of the algorithm, for people hitting the exact issue that I had, but let me write the conclusion of this blog post: even if SQL is awesome in sorting and indexing, it doesn't mean that is the only solution. In my case, the SQL indexes proved to be a golden hammer that wasted days of my work.

So, the logic here is really simple, which makes this entire endeavour educational, but really frustrating to me:

1. Sort the table by start IP ascending, then end IP descending - this makes the parents come before the children in the list
2. Create a table variable to store the previous parents - so when you finished with a range you will automatically find yourself in its parent
3. Use a cursor to move through all the items and for each one:
4. Remove all parents that ended before the current item starts - removes siblings for the list
5. Get the last parent in the list - that is the current parent range
6. Set the parent id to be the one of the last parent

It's that deceptively simple and the query now ends in 15 minutes instead of days.

Another issue that might be interesting is that after the original import is created, the new records added to the table should be just a few. In that case, the first join and update might work faster! The next thing that I will do is count how many items I need to update and use one method or another based on that.

Hope that helps someone.

Read More

Villains by Necessity, by Eve Forward

Villains by Necessity is not a masterpiece of literature, but it is a fun fantasy book that doesn't feel the need to be part of a trilogy or take itself too seriously. Perfect for when you want to pick up a book because you are tired, not because you want to work your brain to dust. First work of Eve Forward, it is rather inconsistent, moving from silly to dead serious and back and making the heroes of the story oscillate between pointlessly evil and uncharacteristically good.

The best part of the book, though, is the concept. The world enjoys an age of light and good after a bitter war that saw all the forces of darkness and evil be defeated. The world is filled with happy people, no conflict, beautiful weather, lush vegetation. In a word, it is fucking boring. An unlikely party of evildoers gets together to save the world by bringing darkness back!

Alas, it was a concept that was not really well used. The characters, borrowed from classical fantasy, are "evil" by their professions only, but not by behaviour. Sam is an assassin, but he doesn't enjoy the suffering of his victims and is proud of his prowess. Archie is a mischievous thief, but other than that he is an OK fellow. Even Valerie, the dark sorceress, eats sentient beings just because it is her race's culture and her evil is more often artificial. Not to mention Blackmail, who acts as the classic stoic hero. Similarly, the forces of good are blood thirsty thugs that want to either kill everything dark or brainwash them, as a humane solution. This basically makes our heroes... err... heroes, not villains, and viceversa.

Now, the book wasn't bad. The style was amateurish, but it is Eve Forward's first book, after all. I could read it and I got caught by the story. I was more attracted to the original concept, though, and I was very curious how it would go. It is so difficult to present bad people as the protagonists, I know, because many people, including writers as they write, want them to be redeemed somehow. In the end, the moral of the story - excruciatingly laid out in a few paragraphs that shouldn't have existed - felt really heavy handed and simplistic. Ok, good people can do bad things and bad people can do good things, but it is important to explore what makes them good and bad, not just lazily assign them dark fantasy classes and be done with it.

Bottom line: fun read, but nothing special.

Read More

We are doomed to be hit by asteroids, repeatedly

This is how reality stands right now: even if the danger of an asteroid hit is great, the risk of one hitting is small. That means that they hit (very) far apart and cause a lot of damage. Now, all governments in the world are run by politicians, who are by their very nature bureaucrats. They are reactive, not proactive, and they have insulated themselves from responsibility by manipulating laws and creating committees and departments that they can behead at any time, as they keep their fat asses on their chairs of power. This is not a rant, it's just the ugly truth, evolving, but never really changing since we were barely smarter than monkeys.

The logical conclusion of these facts is that politicians will not do anything about asteroids until we are hit by one. Even worse, since the probability that a really big one will hit without us knowing in advance has been reduced by space advances, the asteroid that will hit us will probably be small. The Tunguska and the Chelyabinsk events, real things that happened, changed nothing. The one that is going to change anything will be when something similar happens on top of a city.

This is not a doomsday prophecy, either. The probability that this will happen is extremely small. First of all the asteroid has to be small enough and/or fast enough so that we don't detect it in time. Then it has to hit at a certain angle to not be deflected by the atmosphere. Then it has to reach a populated area, which one would think is simple, since we can't seem to be able to fart without someone smelling it, but in truth, with the oceans and the human propensity of congregating for no good reason, it is less probable. However, with enough time, even a small probability becomes certainty.

So, the scenario goes like this: we all pretend to care, but we don't. We want less taxes, not asteroid protection. Politicians use our shortsightedness and our greed to enhance their own and do nothing. Then an asteroid hits, causing massive damage, death and loss of property. This is the moment when something happens. They implement new laws, launch asteroid defense programs, create new departments and committees. But, since the probability that an asteroid hits is small, the hype will fade, the budgets with it, politicians will rotate, people will forget. By the time the next asteroid hits, no one will be prepared for it any more than for the previous one.

In the end, the only things that ever made a dent in the probability that something will hurt us as a species or even as a larger group were technological. Not technology per se, just its price. Just more scientists with cheaper tech getting more done. When space launches become cheaper, satellites smaller, we can do more with them at the same relative price. That is why now we are discovering millions of asteroids in the Solar System, not because of some sort of scientific awakening. It's cheaper, probably as cheap as it was for amateur astronomers to buy telescopes in 1801, when Giuseppe Piazzi discovered the first asteroid, Ceres. I just hope this all gets cheap enough fast enough so we can do something by the time the big asteroid is coming. Well, if we don't destroy ourselves in some other way by then.

I know I'm a month late, but Happy Asteroid Day!

Read More

Fun debugging stuff

I needed to get all IP addresses in a range, so I applied the mask to my current IP and started to work through the minimum and maximum values of bytes to get the result. I had a code that looked like this:

for (var b = min; b <= max; b++) { //do stuff }

where min was 0 and max was 255.

The expected result: all values from 0 to 255. The result: infinitely running code. Can you spot why?

Yes, when min and max are bytes, b is also a byte, so when it gets to 255 and does b++ the value becomes 0 again. Fun, eh?

Read More

The White Luck Warrior (Aspect Emperor book 2), by R. Scott Bakker

There are several stories happening at the same time in The White Luck Warrior, with almost no direct connection between them. There is the Great Ordeal, advancing slowly towards Golgoterath while being besieged by hordes of Sranc, also containing the story of this kid prince forced to march with it; then there is the palace life, with Esmenet left to rule the empire while Kellhus is away, while various factions are ready to take advantage of the lack of man power of the leadership and her half Dunyain children prove to be either insane or really insane; there is the trek of Achamian in search of the origin place of Kellhus. Among these there is a vague and a few paragraphs long subplot of The White Luck Warrior, a mysterious figure that seems to know all of its future, making him an automaton, I guess and some bits about the Fanim.

Why the smallest and insignificant portion of the book gave its title I do not know, but remember that the first book in the Aspect-Emperor series was called The Judging Eye, which is most prominently used or described in this volume. By far the most interesting and captivating storyline is that of Achamian, although I have to say that the logistics of long duration travel within enemy territory and the psychological factors involved seemed to me poorly described by Bakker.

What I knew will happen happened. I finished the book before the third volume in the series was released and now I am in withdrawal pains. That proves that the book captivated me. At very few moments I felt the need to "fast forward" and, considering the amount of distraction and that I had resolved to draw this book out a little bit in the hope that the third volume would be released, I finished it rather quickly.

Even if enjoyable, to me it felt more like a filler. I couldn't empathize with Esmenet or any of her demented children, nor could I care less what happened to Maithanet, who is one of the less fleshed out characters in the book. Similarly, the Sorweel story arch described a confused and frustrated teen, which was relatable, but uninteresting as a character. Unlike in the first four books, Kellhus sounds less godly and dominating and is mostly relegated to a minor role in the overall story. No, the most interesting characters and storyline revolve around Achamian, Mimara, The Captain and the mysterious Cleric, plus any of other members of the crazy bunch of mercenaries known as The Skin Eaters. And they just walk and walk and walk, only to end the book in a cliffhanger. While I await eagerly the sixth book, I have my misgivings and fears that it will not be as good as this one, just as this one felt a little bit short of the first.

Read More

Possible SQL injection using SQL parameters

This post will discuss the possibility of creating an SQL injection using the name of a parameter.

We have known about SQL injection since forever: a programmer is constructing an SQL command using user provided information and some malicious hacker inserts a specially crafted string that transforms the intended query into something that returns the content of a user table or deletes some data on the server. The solution for this, in the .NET world, is to use parameterized queries. Even if someone dynamically creates an SQL query, they should use parameter names and then provide the parameters to the SQL command. The idea behind this is that any value provided by the users will be escaped correctly using parameters. Today I found that this solution works perfectly for parameter values, but less perfectly for parameter names. Try to use a parameter with a name containing a single quote and you will get an error. Let's analyse this.

Here is a piece of code that just executes some random SQL text command, but it also adds a parameter containing a single quote in the name:

using (var conn = new SqlConnection("Server=localhost;Database=Test;UID=sa;Trusted_Connection=True;"))
{
    conn.Open();
    using (var comm = new SqlCommand())
    {
        var paramName = "a'";

        comm.Connection = conn;
                    
        comm.CommandText = "SELECT 1";
        comm.Parameters.Add(new SqlParameter(paramName, SqlDbType.NVarChar, 100)
        {
            Value="text"
        });

        comm.ExecuteNonQuery();
    }
    conn.Close();
}

As you can see, the text content of the SQL command is irrelevant. the name of the parameter is important and for this I just used a single quote in the name. Running SQL Profiler, we get this query string that is actually executed:

exec sp_executesql N'SELECT 1',N'@a'' nvarchar(100)',@a'=N'text'

In this example the name of the parameter is properly handled in the string defining the name and type of the parameters, but it is NOT escaped during the parameter value declaration. A small change of the code with paramName="a='';DELETE * FROM SomeTable --" results in an interesting query string in the SQL Profiler:

exec sp_executesql N'SELECT 1',N'@a='''';DELETE FROM SomeTable -- nvarchar(100)',@a='';DELETE FROM SomeTable --=N'text'

Strangely enough, when inspecting the SomeTable table, the values are still there, even if copying the text into SQL Management Studio actually deletes the values. A similar construction using stored procedures leads to a completely legal SQL that is recorded by SQL Profiler, but it doesn't really do anything:

using (var conn = new SqlConnection("Server=localhost;Database=Test;UID=sa;Trusted_Connection=True;"))
{
    conn.Open();
    using (var comm = new SqlCommand())
    {
        var paramName = "a='';DELETE FROM SomeTable --";

        comm.Connection = conn;
        comm.CommandText = "DoTest";
        comm.CommandType = CommandType.StoredProcedure;
        comm.Parameters.Add(new SqlParameter(paramName, SqlDbType.NVarChar, 100)
        {
            Value="text"
        });

        int k = 0;
        using (var reader = comm.ExecuteReader())
        {
            while (reader.Read()) k++;
        }
        Console.WriteLine(k);
    }
    conn.Close();
}

... with the resulting SQL:

exec DoTest @a='';DELETE FROM SomeTable --=N'text'

I have demonstrated a method of sending a maliciously crafted parameter name to the SqlCommand class and managing to send to the SQL Server a query that should achieve a destructive result. So why doesn't it actually do anything?

The explanation is in the EventClass column of the SQL Profiler. While a normally executed SQL command (let's say from SQL Management Studio) has event classes of SQL:BatchStarting and SQL:BatchCompleted, the query resulting from my attempts have an EventClass of RPC:Completed. It appears that the RPC method of sending queries to the SQL Server doesn't allow for several commands separated by a semicolon. The result is that the first command is executed and the rest are apparently being ignored. The TDS protocol documentation shows that the RPC method is a system of executing stored procedures by sending a binary structure that contains stuff like the name of the procedure, the parameters and so on. Since an SQL text is actually translated into a call to the sp_executesql stored procedure, RPC is used for both types of SqlCommand: Text and StoredProcedure.

I don't have the time to explore this further, but I wonder if this can be used for any type of SQL injection. To make sure, try to check the names of the parameters, if they come from user input.

Read More