Find Missing Number with Vector

c plus plusThis one is simple, given an array containing all numbers from 1 to N with the exception of one print the missing number to the standard output. My solution makes use of vector. Expected complexity is O(N). As a side note, it has been said that this problem has been asked on Microsoft interviews.

 


#include <iostream>
#include <vector>

using namespace std;

void find_missing_number(const vector<int> &v) {
int total, i;
total  = (v.size()+1)*(v.size()+2)/2;
for (i = 0; i < v.size(); i++)
total -= v[i];
cout <<  total;
}

Finding the Longest Palindrome

The other day I was doing a programming challenge that required me to find the longest palindrome within a string. The challenge was to do it in at least O(N)2 complexity.  I found this to be fairly interesting. The challenge read like so:

Given a string S, find the longest substring in S that is the same in reverse and print it to the standard output.

So for example, if I had the string given was:  s= “abcdxyzyxabcdaaa” . Then the longest palindrome within it is “xyzyx “. We need to write a function to find this for us.  The nature of the challenge just needed me to write a function for a web back-end, so the example code below does not have main, or a defined string, etc. Also, there are O(N) solutions for this problem if you seek them, but they are a little more complicated.

#include <iostream>
#include <string>

using namespace std;

void longest_palind(const string &s) {
int n = s.length();
int longestBegin = 0;
int maxLen = 1;
bool table[100][100] = {false};

for (int i = 0; i < n; i++)
{
table[i][i] = true;
}
for (int i = 0; i < n-1; i++)
{
if (s[i] == s[i+1]) {
table[i][i+1] = true;
longestBegin = i;
maxLen = 2;
}
}
for (int len = 3; len <= n; len++) {
for (int i = 0; i < n-len+1; i++) {
int j = i+len-1;
if (s[i] == s[j] && table[i+1][j-1]) {
table[i][j] = true;
longestBegin = i;
maxLen = len;
}
}
}
cout << s.substr(longestBegin, maxLen);
}

OverTheWire Leviathan Wargame Solution 2

Originally posted on Demux:

Leviathan2 presents us with a small binary that belongs to the user leviathan3 and group leviathan2. The program contains a small security hole that can be exploited using a symbolic link.  To understand how the program functions at its core and what is happening behind the scenes when the program executes, we will use a few Linux commands and techniques to enlighten us with this information.

Edited: 3/18/2014:

  • Updated with current solution
  • Made more readable

Leviathan 2->3:

1
leviathan2@melinda:~$ ls -la
total 28
drwxr-xr-x 2 root root 4096 Jun 6 2013 .
drwxr-xr-x 160 root root 4096 Oct 17 09:23 ..
-rw-r--r-- 1 root root 220 Apr 3 2012 .bash_logout
-rw-r--r-- 1 root root 3486 Apr 3 2012 .bashrc
-rw-r--r-- 1 root root 675 Apr 3 2012 .profile
-r-sr-x--- 1 leviathan3 leviathan2 7365 Jun 6 2013 printfile

#Running "printfile" we can see that it wants a file path
#argument:

leviathan2@melinda:~$…

View original 510 more words

OverTheWire Natas Wargame Solutions 7-10

Let’s continue our progression through the Natas wargame server. The challenges ahead are slightly more difficult than the previous challenges which is why I chose to break where I did. Nevertheless, they are not impossible. Some entry level knowledge of PHP would go a long way here. Examine my solutions below:

Natas 6->7

Here we have an insecure PHP login form. Looking at the source, we can see that whatever we enter as the input secret is being compared to variable $_POST, within the PHP script. We also see the file “include/secret.inc is mentioned. We can tac that on to the end of our URL to see what it contains. Immediately, we will see it holds the secret variable “FOEIUWGHFEEUHOFUOIU”. Our script uses this variable to compare the input secret to, which means it is our password. Remember you need to change the URL to Natas7 to get access.

FOEIUWGHFEEUHOFUOIU

 

Natas 7->8

Now we are presented with a very nondescript web page containing two tabs, home and about. If we travel to the about page, and examine the source, we see a huge clue. It’s an HTML comment telling us that the password is held in /etc/natas_webpass/natas8. Awesome. But if you tac it on to the end of the URL like we have previously been doing it will not redirect you there. You need to tac it on the end of the”page=” variable.

http://natas7.natas.labs.overthewire.org/index.php?page=/etc/natas_webpass/natas8

DBfUBfqQG69KvJvJ1iAbMoIpwSNQ9bWe

Natas 8->9

Moving along we come across another PHP login form. Viewing the source we something that should catch your interest, the variable: $encodedSecret = “3d3d516343746d4d6d6c315669563362″;. This is going to be our password, insecurely stored, but encoded nevertheless. It is encoded with the function “encodeSecret” shown below.

Natas 8
The script Base64 encodes the secret->reverses that->then calls bin2hex() on that. We can actually use this script, in reverse order to get our secret. Create the script in a .php file like so:

<!--?php echo base64_decode(strrev(hex2bin("3d3d516343746d4d6d6c315669563362"))); ?-->

There are a couple of ways to run the script. If you are on some Linux flavor, and have PHP installed. You can run it inside your shell like this:

 php -f natas8.php

Or, if you have some web server like XAMPP or Apache/HTTPD installed, you can throw the script in /htdocs and simply navigate to the script. You will see the password as soon as you land on the page. It’s worth noting having a local web server is useful for many reasons.

oubWYf2kBq

Natas 9->10

Natas 9 presents us with a search form. Examining the source code, we see another PHP script.

Natas10

 

 

 

 

 

We are not concerned with the fact that the form searches a dictionary file called dictionary.txt. Rather, we are interested in the fact the search form executes commands on the server. So, how can we leverage this?

We see that the script is greping the dictionary file. A little known fact about executing commands in this fashion is that we can chain commands together by using the shell command separator ;. Thinking back to Natas 7, we learned that the passwords are stored in /etc/natas_webpass/respectiveLevel. Let’s construct a chained command using this knowledge:

grep -i ; cat /etc/natas_webpass/natas10 # dictionary.txt

We used an additional argument in our command chain, the # operator.  That is used to comment anything after that operator. Thus, restricting our search to only /etc/natas_webpass/natas10. Finally, we are presented with our password:

nOpp1igQAkUzaI1GUUjzn1bFVj7xCNzu

OvertheWire Natas Wargame Solutions 0-6

The Natas series of games presents us with some challenges you might encounter while auditing serverside web-security. For the most part, they are examples of what programmers and administrators should not do. I will break up the challenges into small groups since there are 27 of them and it would be a great deal of writing. Serverside web-security is relevant to us because it is something users encounter most often. Every time you browse the web and interact with web applications, you are conversing with these protection mechanisms. Let’s take a look at the solutions to the following Natas challenges:

Natas 0->1

This one is easy enough, the password is on the page it says. View source and we can see the password in an html comment:

<!--The password for natas1 is gtVrDuiDfck831PqWsLEZy5gyDz1clto -->

Natas 1->2

The password for this one is found via the same method, except right-clicking has been blocked. It is blocked via JavaScript, so either disabling JavaScript in your browser or if you are like me and use a browser plugin like NoScript, you will be able to right-click anyway.

<!--The password for natas2 is ZluruAthQk7Q2MqmDeTiUij2ZvWy2mBi -->

Natas 2->3

Finding the password for Natas 3 requires us to explore a little more. Viewing the source, we see a couple of things: our Natas 2 pass embedded in some JavaScript and a link to a pixel image. We are not interested in the image itself, but the directory it is in. We can append /files to the end of our url and see the directory is readable. If we navigate to the users.txt file, we will see the password for Natas 3:

 sJIJNW6ucpu6HPZ1ZAchaDtwd7oGrD14

Natas 3->4

Viewing the source of this problem we can see an HTML comment “No more information leaks!! Not even Google will find it this time”. We can take that to mean the robots.txt file that is meant to disallow web bots from viewing certain directories within websites, if they decide to follow the rules… Navigating to /robots.txt we can see that the directory /s3cr3t/ is disallowed. Luckily for us, it is readable when navigating to it. Within you will see the users.txt file with the password for Natas 4:

Z9tkRkWmpt9Qr7XrR5jWRkgOU901swEZ

Natas 4->5

Natas 4 presents us with a referral issue. It is blocking users being referred from anything other than http://natas5.natas.labs.overthewire.org/. For this we will use a Firefox browser plugin RefControl (You are using Firefox aren’t you?). Open up the RefControl options, add new site: http://natas4.natas.labs.overthewire.org/. Add a custom option with this in it: http://natas5.natas.labs.overthewire.org/. Press okay and refresh the page. We are magically presented with an access granted message and the password for Natas 5:

iX6IOfmpN7AYOQGPwtn3fXpbaJVJcHfq

Natas 5->6

Now we are presented with a nondescript message ” Access disallowed. You are not logged in”. What could this really mean? If you guessed it has something to do with cookies, you were right. For problems like this, I use the awesome Firefox extension Firebug . Firebug now comes with the extension Firecookie, which allows on-the-fly viewing and editing of cookies in your browser. Install Firebug, right-click the page, and click on the cookies tab. You will see a cookie named “loggedin” for the natas5 domain. We can see it’s value is set to “0”. Let’s edit that and set it’s value to true or “1”. Do that, refresh the page, and we can now see the message “Access granted. The password for natas6″

 aGoY4q2Dc6MgDq4oL4YtoKtyAg9PeHa1

Installing AMD Catalyst in Fedora 20

Recently I did a fresh install of the Fedora 20 KDE spin. One of the things that I did not realize when installing Fedora 20 was that the AMD Catalyst package is no longer supported. What am I supposed to do? It seems the last available support in any rpm repos was for F19. Browsing the forums I could see a lot of people doing some editing and hacking attempting to get the older packages to work. Seeing all this, the old engineering adage came to mind, “if you’re trying too hard it’s because you are doing it wrong”.

Now don’t get me wrong, I would love to have the open source Radeon driver running on my box, but it simply doesn’t compare to the proprietary driver right now. My machine runs cooler with the proprietary driver and I have better video and graphics performance. So how do I get my ATI card working on my Fedora 20 install you ask? Here are the details:

Installing AMD Catalyst on Fedora 20:

For starters, you will need to have some prerequisite packages installed to get the driver working:

# yum install gcc binutils make kernel-devel kernel-headers

Secondly, you will want to grab AMD Catalyst 13.11 beta from AMD, unzip it and make it executable:

wget –-referer=’http://support.amd.com/en-us/download/desktop?os=Linux+x86&#8242; http://www2.ati.com/drivers/beta/amd-catalyst-13.11-betav9.95-linux-x86.x86_64.zip

# unzip amd-catalyst-13.11-betav9.95-linux-x86.x86_64.zip

# chmod a+x amd-catalyst-13.11-betaV9.95-linux-x86.x86_64.run

Within your root terminal, navigate to your package and run the .run file:

# ./amd-catalyst-13.11-betaV9.95-linux-x86.x86_64.run

You should be installing the driver with no hitch now. (If running Gnome, see possible caveats below). After you have rebooted, check it went okay with this command $ fglrxinfo, though I can visually discern the driver is working because my screen resolution is correct and much, much better looking.

Here is some sample output from my box:

[demux@localhost ~]$ fglrxinfo
 display: :0  screen: 0
 OpenGL vendor string: Advanced Micro Devices, Inc.
 OpenGL renderer string: ATI Radeon HD 5670
 OpenGL version string: 4.3.12615 Compatibility Profile Context 13.25.18

Possible Caveats:

There are always caveats right? I only know of this working on XFCE and KDE, though it should work with others. However, there are reports that Gnome installs may run into some problems. This is apparently because Gnome has made provisions in their code to embrace the Wayland display server. The code within that is reported to conflict with the ATI code.

Also, you may have to re-install Catalyst after a kernel update. Though so far, I have not needed to. But it is possible. Dkms might allow the kernel to automatically incorporate the drive in new kernels, but I have not tested this or needed it thus far. If worse comes to worse, you will need to re-run the .run file. This method of install should work for future versions of Fedora as well and is really a general method of install for the proprietary driver.

C++ Primer Plus Chapter 7 Exercise 9

c plus plusChapter 7 ends with a short exercise on function pointers. The simplest way to complete this, which I provided in my source, is to create the two functions add() and calculate(), then call them in main() with a loop. The text mentions if you are feeling adventurous to include other functions in addition to add. For simplicities sake, I did the minimum requirement here. Finally,  we can put this chapter to rest. See my source below:

9. Design a function calculate() that takes two type double values and a pointer to a function that takes two double arguments and returns a double. The calculate() function should also be type double, and it should return the value that the pointed-to function calculates, using the double arguments to calculate(). For example, suppose you have this definition for the add() function: double add(double x, double y){return x + y}. Then, the function call in double q = calculate(2.5, 10.4, add); would cause calculate() to pass the values 2.5 and 10.4 to the add() function and then return the add() return value (12.9). Use these functions and at least one additional function in the add() mold in a program. The program should use a loop that allows the user to enter pairs of numbers. For each pair, use calculate() to invoke add() and at least one other function. If you are feeling adventurous, try creating an array of pointers to add()-style functions and use a loop to successively apply calculate() to a series of functions by using these pointers. Hint: Here’s how to declare such an array of three pointers: double (*pf[3])(double, double); You can initialize such an array by using the usual array initialization syntax and function names as addresses.

#include <iostream>

using namespace std;

double calculate(double x, double y, double (*pf)(double a, double b));
double add(double x, double y);

int main()
{
double x, y;
cout << "Enter two numbers (q to exit): ";
while(cin >> x >> y)
{
if(cin.fail())
break;
calculate(x, y, add);
cout << "The sum is: " << calculate(x, y, add) << "\n\n";
}
return 0;
}

double calculate(double x, double y, double (*pf)(double a, double b))
{
return pf(x, y);
}

double add(double x, double y)
{
return x + y;
}