Hello WordPress.com

This is the third reincarnation of this website.  It’s amazing how time flies by.

V1

Built early 2007 on websitebaker, I self hosted this on various available university computers. At the time I was working as a Linux sysadmin and going to school. I liked websitebaker because of how simple it was to customize and figure out how it worked.  Here is a post on the theme.

V2

Built in mid 2009 when I was leaving the university to go work for IOActive in Seattle, I needed a new place for hosting which I had been getting for free. I went with site5 largely because it was cheap (around $5/month), and it had ssh access so I could migrate fairly easily (e.g. leaving all files in the same structure). I also migrated from websitebaker to wordpress, which is a huge improvement in my opinion. With the wife’s help, I wrote the Ryu theme as a modification of the existing theme.

V3

I don’t get a lot of traffic, but when I do get bursts then site5 seems to struggle. I’m working on some things I think are neat lately (coming soon! I’m planning on putting more effort here than I ever have before)  and I want the website to stay responsive if I ever get slashdotted or something. I ultimately wanted to stay with wordpress as the cms but was willing to try others. I looked at/considered EC2, Media Temple, and Blogger. In the end, I think WordPress.com is the best fit. It has a low price tag ($30/yr for no ads, $30/yr for custom css, and $15/yr so I can use my domain). Besides scalability, I just feel like if I tried I could hack site5 and that scares me. I did find a wordpress bug one time, but when I was looking for it I was pretty impressed with the general code quality.

My big reservation with wordpress.com was that I couldn’t upload arbitrary files to share, but with things like skydrive (which I use), dropbox, google drive, and Amazon’s services it make sense to separate that piece and link to that content. I spent a lot of time this weekend working to get the new setup (my lovely wife also helped with the CSS), and I think it’s generally looking pretty good :)

8-queens problem hill climbing python implementation

It was written in an AI book I’m reading that the hill-climbing algorithm finds about 14% of solutions. I implemented a version and got 18%, but this could easily be due to different implementations – like starting in random columns rather than random places on the board, and optimizing per column. Anyway, here is the program.

README

This program is a hillclimbing program solution to the 8 queens problem. The algorithm is silly in some places, but suits the purposes for what I was working on I think. It was tested with python 2.6.1 with psyco installed. If big runs are being tried, having psyco may be important to maintain sanity, since it will speed things up significanlty. Otherwise, you may want to stick to –numrun being less than around 50.

The board is simply defined as a two dimensional list, with the occupied elements stored as “Q” and empty emements as 0. The initial board is generated by picking a random row and column to place a queen, although the class structure allows for predefined boards to be manually passed in. If the spot on the board is occupied, then another spot is randomly chosen.

Violations are calculated by iterating through every queen and checking horizontally, vertically, and diagonally for other queens. Each violation is totalled up, and at the end they are divided by 2 since violations were overcounted. This could certainly be optimized further.

The hill solution works by checking every possible single move and returning the best of these. Obviously, this could also be improved upon. The book’s algorithm (which was not available while programming this) simply attempts to move every space within a column rather than every open spot on the board – which would speed up the process by an order of magnitude and also decrease the likelihood of finding a solution by a small percentage. Also, it appears that the random initial state only contains one queen per column, which is also different from this implementation. The assignment specification mentions a randomly generated board, which is what this implementation was based on. If an implementation closer to that of the book is desired, please let me know, as it would only be a minor adjustment.

With this algorithm, every queen on the board tries to move to every spot on the board, and violations are re-calculated. A move with the least violations is chosen and the process repeats until there is no improvement. It there is no improvement after every queen has had a go, there is no solution found and the algorithm returns. If there is an improvement, the algorithm continues for another go-around.

The biggest run so far is just 1000 nodes. It returned 175 successes, which is fairly close to the book’s given percentage or .14.

Here is sample usage:

mopey-mackey:hillclimb user$ python eight_queen.py –help
Usage: eight_queen.py [options]

Options:
-h, –help show this help message and exit
-q, –quiet Don’t print all the moves… wise option if using large
numbers
–numrun=NUMRUN Number of random Boards

mopey-mackey:hillclimb user$ python eight_queen.py –numrun=1000 –quiet
Total Runs: 1000
Total Success: 175
Success Percentage: 0.175
Average number of steps: 3.83

mopey-mackey:hillclimb user$ python eight_queen.py
====================
BOARD 0
====================
Board Violations 7
0 0 Q 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 Q 0 0
Q 0 0 0 0 0 0 0
0 0 0 0 Q 0 0 0
Q Q 0 0 0 0 Q 0
0 0 0 0 0 0 0 0
0 0 0 0 Q 0 0 0

Board Violations 4
0 0 Q 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 Q 0 0
Q 0 0 0 0 0 0 0
0 0 0 0 Q 0 0 0
Q Q 0 0 0 0 0 0
0 0 0 0 0 0 0 Q
0 0 0 0 Q 0 0 0

Board Violations 3
0 0 Q 0 0 0 0 0
Q 0 0 0 0 0 0 0
0 0 0 0 0 Q 0 0
0 0 0 0 0 0 0 0
0 0 0 0 Q 0 0 0
Q Q 0 0 0 0 0 0
0 0 0 0 0 0 0 Q
0 0 0 0 Q 0 0 0

Board Violations 2
0 0 Q 0 0 0 0 0
Q 0 0 0 0 0 0 0
0 0 0 0 0 Q 0 0
0 Q 0 0 0 0 0 0
0 0 0 0 Q 0 0 0
0 Q 0 0 0 0 0 0
0 0 0 0 0 0 0 Q
0 0 0 0 Q 0 0 0

NO SOLUTION FOUND
Total Runs: 1
Total Success: 0
Success Percentage: 0.0
Average number of steps: 4.0

mopey-mackey:hillclimb user$ python eight_queen.py –numrun=4
====================
BOARD 0
====================
Board Violations 3
0 0 Q 0 0 0 0 0
Q 0 0 0 Q 0 0 0
0 0 0 0 0 0 0 Q
0 0 0 Q 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 Q 0
0 Q 0 0 0 0 0 0
0 0 0 0 0 0 0 Q

Board Violations 1
0 0 Q 0 0 0 0 0
Q 0 0 0 Q 0 0 0
0 0 0 0 0 0 0 Q
0 0 0 Q 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 Q 0
0 Q 0 0 0 0 0 0
0 0 0 0 0 Q 0 0

Board Violations 0
0 0 Q 0 0 0 0 0
0 0 0 0 Q 0 0 0
0 0 0 0 0 0 0 Q
0 0 0 Q 0 0 0 0
Q 0 0 0 0 0 0 0
0 0 0 0 0 0 Q 0
0 Q 0 0 0 0 0 0
0 0 0 0 0 Q 0 0

SOLUTION FOUND
====================
BOARD 1
====================
Board Violations 8
Q 0 0 0 0 0 0 Q
0 0 0 0 0 0 Q 0
0 0 Q 0 Q 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 Q 0 0
0 0 0 0 0 0 0 0
0 Q 0 0 Q 0 0 0
0 0 0 0 0 0 0 0

Board Violations 5
Q 0 0 0 0 0 0 Q
0 0 0 0 0 0 Q 0
0 0 Q 0 Q 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 Q 0 0
0 0 0 0 0 0 0 0
0 0 0 0 Q 0 0 0
0 Q 0 0 0 0 0 0

Board Violations 3
0 0 0 0 0 0 0 Q
0 0 0 0 0 0 Q 0
0 0 Q 0 Q 0 0 0
Q 0 0 0 0 0 0 0
0 0 0 0 0 Q 0 0
0 0 0 0 0 0 0 0
0 0 0 0 Q 0 0 0
0 Q 0 0 0 0 0 0

Board Violations 2
0 0 0 0 0 0 0 Q
0 0 0 0 0 0 Q 0
0 0 Q 0 0 0 0 0
Q 0 0 0 0 0 0 0
0 0 0 0 0 Q 0 0
Q 0 0 0 0 0 0 0
0 0 0 0 Q 0 0 0
0 Q 0 0 0 0 0 0

NO SOLUTION FOUND
====================
BOARD 2
====================
Board Violations 5
0 Q 0 Q 0 0 0 0
0 0 0 0 0 Q 0 Q
Q 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
Q 0 0 0 0 0 0 0
Q 0 0 0 0 0 0 0
0 0 0 0 0 0 Q 0
0 0 0 0 0 0 0 0

Board Violations 3
0 Q 0 Q 0 0 0 0
0 0 0 0 0 Q 0 Q
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
Q 0 0 0 0 0 0 0
Q 0 0 0 0 0 0 0
0 0 0 0 0 0 Q 0
0 0 0 0 Q 0 0 0

Board Violations 2
0 Q 0 Q 0 0 0 0
0 0 0 0 0 Q 0 0
0 0 0 0 0 0 0 Q
0 0 0 0 0 0 0 0
Q 0 0 0 0 0 0 0
Q 0 0 0 0 0 0 0
0 0 0 0 0 0 Q 0
0 0 0 0 Q 0 0 0

Board Violations 1
0 Q 0 Q 0 0 0 0
0 0 0 0 0 Q 0 0
0 0 0 0 0 0 0 Q
0 0 Q 0 0 0 0 0
Q 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 Q 0
0 0 0 0 Q 0 0 0

Board Violations 0
0 Q 0 0 0 0 0 0
0 0 0 0 0 Q 0 0
0 0 0 0 0 0 0 Q
0 0 Q 0 0 0 0 0
Q 0 0 0 0 0 0 0
0 0 0 Q 0 0 0 0
0 0 0 0 0 0 Q 0
0 0 0 0 Q 0 0 0

SOLUTION FOUND
====================
BOARD 3
====================
Board Violations 5
0 0 0 Q Q 0 0 0
0 0 0 0 0 0 0 Q
0 0 0 0 0 0 0 0
0 0 0 0 0 Q 0 0
0 0 0 0 0 0 0 Q
0 Q 0 0 0 0 0 0
0 0 0 0 Q 0 0 0
0 0 Q 0 0 0 0 0

Board Violations 3
0 0 0 0 Q 0 0 0
0 0 0 0 0 0 0 Q
0 0 0 Q 0 0 0 0
0 0 0 0 0 Q 0 0
0 0 0 0 0 0 0 Q
0 Q 0 0 0 0 0 0
0 0 0 0 Q 0 0 0
0 0 Q 0 0 0 0 0

Board Violations 1
0 0 0 0 Q 0 0 0
Q 0 0 0 0 0 0 0
0 0 0 Q 0 0 0 0
0 0 0 0 0 Q 0 0
0 0 0 0 0 0 0 Q
0 Q 0 0 0 0 0 0
0 0 0 0 Q 0 0 0
0 0 Q 0 0 0 0 0

Board Violations 0
0 0 0 0 Q 0 0 0
Q 0 0 0 0 0 0 0
0 0 0 Q 0 0 0 0
0 0 0 0 0 Q 0 0
0 0 0 0 0 0 0 Q
0 Q 0 0 0 0 0 0
0 0 0 0 0 0 Q 0
0 0 Q 0 0 0 0 0

SOLUTION FOUND
Total Runs: 4
Total Success: 3
Success Percentage: 0.75
Average number of steps: 4.0

And here is the source

#!/usr/bin/python

import random,sys,copy
from optparse import OptionParser
try:
  import psyco
  psyco.full()
except ImportError:
  pass

"""
cowboy code, but seems to work
USAGE: python prog <numberruns=1> <verbocity=False>
"""

class board:
  def __init__(self, list=None):
    if list == None:
      self.board = [[0 for i in range(0,8)] for j in range(0,8)]
      #initialize queens at random places
      for i in range(0,8):
        while 1:
          rand_row = random.randint(0,7)
          rand_col = random.randint(0,7)
          if self.board[rand_row][rand_col] == 0:
            self.board[rand_row][rand_col] = "Q"
            break
    #TODO raise errors if board is not right format or dimension
  #define how to print the board
  def __repr__(self):
    mstr = ""
    for i in range(0,8):
      for j in range(0,8):
        mstr = mstr + str(self.board[i][j]) + " "
      mstr = mstr + "n"
    return (mstr)

class queens:
  def __init__(self, numruns, verbocity, passedboard=None):
    #TODO check options
    self.totalruns = numruns
    self.totalsucc = 0
    self.totalnumsteps = 0
    self.verbocity = verbocity
    for i in range(0,numruns):
      if self.verbocity == True:
        print "===================="
        print "BOARD",i
        print "===================="
      self.mboard = board(passedboard)
      self.cost = self.calc_cost(self.mboard)
      self.hill_solution()

  def hill_solution(self):
    while 1:
      currViolations = self.cost
      self.getlowercostboard()
      if currViolations == self.cost:
        break
      self.totalnumsteps += 1
      if self.verbocity == True:
        print "Board Violations", self.calc_cost(self.mboard)
        print self.mboard
    if self.cost != 0:
      if self.verbocity == True:
        print "NO SOLUTION FOUND"
    else:
      if self.verbocity == True:
        print "SOLUTION FOUND"
      self.totalsucc += 1
    return self.cost

  def printstats(self):
    print "Total Runs: ", self.totalruns
    print "Total Success: ", self.totalsucc
    print "Success Percentage: ", float(self.totalsucc)/float(self.totalruns)
    print "Average number of steps: ", float(self.totalnumsteps)/float(self.totalruns)

  def calc_cost(self, tboard):
    #these are separate for easier debugging
    totalhcost = 0
    totaldcost = 0
    for i in range(0,8):
      for j in range(0,8):
        #if this node is a queen, calculate all violations
        if tboard.board[i][j] == "Q":
          #subtract 2 so don't count self
          #sideways and vertical
          totalhcost -= 2
          for k in range(0,8):
            if tboard.board[i][k] == "Q":
              totalhcost += 1
            if tboard.board[k][j] == "Q":
              totalhcost += 1
          #calculate diagonal violations
          k, l = i+1, j+1
          while k < 8 and l < 8:
            if tboard.board[k][l] == "Q":
              totaldcost += 1
            k +=1
            l +=1
          k, l = i+1, j-1
          while k < 8 and l >= 0:
            if tboard.board[k][l] == "Q":
              totaldcost += 1
            k +=1
            l -=1
          k, l = i-1, j+1
          while k >= 0 and l < 8:
            if tboard.board[k][l] == "Q":
              totaldcost += 1
            k -=1
            l +=1
          k, l = i-1, j-1
          while k >= 0 and l >= 0:
            if tboard.board[k][l] == "Q":
              totaldcost += 1
            k -=1
            l -=1
    return ((totaldcost + totalhcost)/2)

  #this function tries moving every queen to every spot, with only one move
  #and returns the move that has the leas number of violations
  def getlowercostboard(self):
    lowcost = self.calc_cost(self.mboard)
    lowestavailable = self.mboard
    #move one queen at a time, the optimal single move by brute force
    for q_row in range(0,8):
      for q_col in range(0,8):
        if self.mboard.board[q_row][q_col] == "Q":
          #get the lowest cost by moving this queen
          for m_row in range(0,8):
            for m_col in range(0,8):
              if self.mboard.board[m_row][m_col] != "Q":
                #try placing the queen here and see if it's any better
                tryboard = copy.deepcopy(self.mboard)
                tryboard.board[q_row][q_col] = 0
                tryboard.board[m_row][m_col] = "Q"
                thiscost = self.calc_cost(tryboard)
                if thiscost < lowcost:
                  lowcost = thiscost
                  lowestavailable = tryboard
    self.mboard = lowestavailable
    self.cost = lowcost

if __name__ == "__main__":

  parser = OptionParser()
  parser.add_option("-q", "--quiet", dest="verbose",
                   action="store_false", default=True,
                   help="Don't print all the moves... wise option if using large numbers")

  parser.add_option("--numrun", dest="numrun", help="Number of random Boards", default=1,
                   type="int")

  (options, args) = parser.parse_args()

  mboard = queens(verbocity=options.verbose, numruns=options.numrun)
  mboard.printstats()

execv-like system call

From the system man page, it explicitely says:

Do not use system() from a program with set-user-ID or set-group-ID privileges, because strange values for some environment variables might be used to subvert system integrity.

Good advice, but sometimes you need to get stuff done anyway. This is experimenting with pam and execv from a stupid insecure google apps pam module I wrote


PID = fork();
if (PID == 0) {
  //child
  char* argvarray[4] = {progarg0, username, newpass, (char *) 0};
  execv(netprog, argvarray);
  if (debug == 1)
    printf("forking failure\n");
  report_error(1);
  return PAM_CRED_ERR;
}
else if (PID < 0) {
  if (debug == 1)
    printf("unexpected error\n");
  report_error(1);
  return PAM_CRED_ERR;
}
 
wait(&amp;execreturn);
//make sure this does exit properly and isn't killed
if (WIFEXITED(execreturn)) {
  rc = WEXITSTATUS(execreturn);
}
else {
  report_error(1);
  return PAM_CRED_ERR;
}

The first 18 lines emulate a system call. The rest is used to get the return value, which you would also need to do with a system call. Basically, it has close to the same functionality as if it were:

system("programcall");
 
wait(&amp;execreturn);
//make sure this does exit properly and isn't killed
if (WIFEXITED(execreturn)) {
  rc = WEXITSTATUS(execreturn);
}
else {
  report_error(1);
  return PAM_CRED_ERR;
}

I thought of a new slogan for cups…

Making the not possible, possible

not_possible

Security in an Insecure Environment

Follow

Get every new post delivered to your Inbox.

Join 33 other followers