02 July 2015

Tail Recursion

Tail recursion is special case of recursion where the function calls itself as the last statement in the method.

From wikipedia:

Tail calls can be implemented without adding a new stack frame to the call stack. 

Here's an example of Sum of Ints function that sum Integers between a and b

so when call sumOfInts(1, 4) would equals 1 + 2 + 3 + 4 = 10

First implementation using non-Tail recursion:

def sumOfInt(a: Int, b: Int): Int =
        if (a > b) 0 else a + sumOfInt(a + 1, b) // last stmt is a call to the same function and then add some value to it (non tail recursion)

The second implementation using a Tail recursion function:

def sumOfInt2(a: Int, b: Int): Int =
        sumOfAllInts(a, b, 0)                    

def sumOfAllInts(a: Int, b: Int, t: Int): Int =
        if (a > b) t else sumOfAllInts(a + 1, b, t + a)  // last stem is a call to the same function only (tail recursion)

Test


sumOfInt(1, 100000000)                        //> java.lang.StackOverflowError
sumOfInt2(1, 100000000)                       //> res2: Int = 987459712


Conclusion

The Tail recursion version using the same stack frame on each call (vs the non-tail recursion which  will use a new stack frame for each call for the reclusive method)

See this question and read the answer to understand about Tail Recursion: http://cs.stackexchange.com/questions/6230/what-is-tail-recursion

29 May 2015

Configure tomcat (on HTTP) to work with HTTPS Load Balancer/Reverse Proxy

Introduction:

The following pattern is common when deploying java webapps on tomcat.

(HTTPS) LB/Reverse Proxy <--> (HTTP)Tomcat <--> Webapp


Usually, the HTTPS certificate is being installed on the Load Balancer/Reverse Proxy, then the LB/RP will communicate with internal tomcat on HTTP/AJP. (see References)

Note:

The following configurations is required only if LB/RP to connect to tomcat on HTTP.

If the communication done on AJP, then no configuration is required to pass HTTPS information to tomcat.

As one of the design goals of AJP is :
"Adding support for SSL, so that isSecure() and getScheme() will function correctly within the servlet container. The client certificates and cipher suite will be available to servlets as request attributes
(quote from https://tomcat.apache.org/connectors-doc/ajp/ajpv13a.html)


Update:

If you use HTTP connector, still the below configuration is not required, just tell tomcat (thought the connector configurations), on which scheme the response should be returned by using:

<Connector protocol="HTTP/1.1" port="8081" proxyName="linux-server" proxyPort="443" scheme="https" secure="true"/>

references: 

There are 2 steps required in case of the communication done on HTTP:

1. On the LB/RP you need to configure it to send its http scheme (in this case https) as a request header to the tomcat servers.

In apache2, you may need to use the following line in apache2.conf (depends on your LB/RP)


RequestHeader add x-forwarded-proto “https”
2. On tomcat side, you need to tell it to use the protocol scheme of the LB/RP that is being sent in the headers.

To do so, you need to add the following valve to conf/server.xml

10 April 2015

About web security (1)

We usually implement web security with Roles and Permissions.

a Database Table for users and one for Roles which users belongs and one for Permission for the roles which the users a role should have.


[Users Table]    <- Many-to-one -> [Roles Table] <-  One-to-many -> [Permissions Table]

The above model is the basic, but we can add extra relation between the Users and the Permissions to allow direct permission on the table regarding the role in which the user belongs.


The Authentication does from the Users table.. the user is there and not disabled.

The Authorization is all about answering the question of "Is the user has access to this restricted object?"

How Authorization done?

In Web - where the restricted object is all about URL resources - the autorization is done as follows:

  • Every resource (a pattern for resources) in the system (should) have a list of permissions associated (usually only one) with it.
    Usually defined in the Permissions table as URL -> PERMISSION mapping. (or in XML as of spring-security)
    ex: '/editMyProfile.html' url mapped to CAN_EDIT_PROFILE permission.
  • When the user successfully login, a list of all permission is attached to him (either role permissions or user permission as discussed before)
  • Then when the user requests some URL, The system checks if the user has some attached permission that in the list of permissions that is associated with the url. If yes then the system allows the user to access the page, otherwise HTTP 403 is returned to the user.

How to draw the menu:

First you have your structure of menu (tree menu, list menu or whatever).
Initially, get all urls from Permissions table of the database and draw this permissions as following:

for (Permission p: permissions){
     if (userHavePermission(p.getPermissionName()){
           out.println(p.getUrl());
     }
}

the above is very simple code example.
Also you can consider nesting the menus by having a self-referential relationship in the Permissions table.










22 January 2015

Two notes about Java Generic Types (Type Covariance and Type erasure)

Java Generics have two characteristics that are important when working with generics of Java.

The first one is the most important and most well-known than the other, the second is less known.

1. Generics types are not Covariant:

All of us knows that List<String> cannot substitute List<Object>; however String[] can substitute Object[]

This prevent error in Generics that happens in case of arrays.

String[] sArr = new String[] {"Hello"};
Object[] oArr = sArr;
oArr[0] = 10; // << Exception in thread "main" java.lang.ArrayStoreException: java.lang.Integer

However in case of Generic types, such error is being caught  at compile time, and this is because Type Parameters (Generics) doesn't allow type covariance.

Example:

List<String> sList = new ArrayList<>();
List<Object> oList = sList; // Type mismatch: cannot convert from List<String> to List<Object>

oList.add(10);

2.  Type parameters is being removed in generated byte code (Called Type erasure).

This is why you cannot say: T.class

Quote: 
When you compile some code against a generic type or method, the compiler works out what you really mean (i.e. what the type argument for T is) and verifies at compile time that you're doing the right thing, but the emitted code again just talks in terms of java.lang.Object - the compiler generates extra casts where necessary. At execution time, a List<String> and a List<Date>are exactly the same; the extra type information has been erased by the compiler.

01 January 2015

Progfun: Union two Binary Trees (week 03)

In Progfun assignment of week3 named "objsets", it is required to write some fast-engouh implementation for the union method.

Note, I am here will not show the solution for this question, I'll just give you the key to find the solution yourself.

Here's the Tree objects:

abstract class TweetSet {
    def union(that: TweetSet): TweetSet
    // other methods here..

}

class Empty extends TweetSet {
    def union(that: TweetSet): TweetSet = that
}

class NonEmpty(elem: Tweet, left: TweetSet, right: TweetSet) extends TweetSet {
    // The is the Not-so-fast implementation from the lectures
    def union(that: TweetSet) = ((left union right) union that) incl elem
}

The question again is to find a better solution for the union method (better in terms of performance as the app with such implementation will took too much time to execute)

Well, since I am not so much good in finding a solution in one shot, I go through more than a step..

First I thought in instead of making the `this` tree to include the `that` tree's nodes, I think of the opposite, which is the `that` tree to include the `this` nodes.

I wrote this -not so good -implementation that is coming from (and based on) the foreach implementation; the foreach implementation is:

def foreach(f: Tweet => Unit): Unit = {
    f(elem)
    left.foreach(f)
    right.foreach(f)

}

So, I thought of an implementation like this, but instead of applying some function to each node, no just add each node to `that` tree, So I wrote this initial implementation:

def union(that: TweetSet): TweetSet = {
    var thatVar = that
    this.foreach { x => thatVar = thatVar.incl(x) }
    thatVar

}

WOW, it worked!, So let's enhance it to comply to the courses rules, which among them is don't use vars and use recursion when possible.

The idea above is for each node in the `this` tree, include it to the `that` tree... pretty simple..

To accomplish this by recursion, we need to do the following:

1. `that` should include the element
2. the result of step #1 should be passed again to the recursion method as `that` and ask `left` start the union process over, then ask `right` to start it over again..

def union(that: TweetSet): TweetSet = ??.union(??.union(?? incl elem))

3. replace the ?? above based on your understanding and you will got the solution.






20 November 2014

Implementing Spring Security with JSF (Login + RedirectStrategy)

When implementing Spring Security in JSF application, many problems happens, and one of the most important one is the redirection in case of HTTP errors!

In this post, I'll take about 2 points, the first point is how to implement the Login page (you will find many resources illustrate this - for example this) but I'll extend it allowing the user to continue on the page he was coming from (aka. Saved Request URL), the second point and the more important one is handling HTTP errors in case of Ajax requests.

Point #1 Handle Login From:

Initially, you have your JSF application (in my case I use Primefaces, but shouldn't matter at all, because the solution is JSF related not primefaces-related)


You have your xhtml login page (login.xhtml) like this:


<html xmlns="http://www.w3.org/1999/xhtml"
    xmlns:h="http://java.sun.com/jsf/html"
    xmlns:f="http://java.sun.com/jsf/core"
    xmlns:p="http://primefaces.org/ui">
<f:view>
    <h:form id="loginForm">
        <h:messages style="color: red;" />

        <table>
            <tr>
                <td><p:outputLabel for="usernameTxt" value="Username" /></td>
                <td><p:inputText id="usernameTxt" value="#{loginBean.username}" /></td>
            </tr>
            <tr>
                <td><p:outputLabel for="passwordTxt" value="Password" /></td>
                <td><p:password id="passwordTxt" value="#{loginBean.password}" /></td>
            </tr>
            <tr>
                <td colspan="2"><p:commandButton value="Login"
                        action="#{loginBean.login}" /></td>
            </tr>
        </table>
    </h:form>
</f:view>

</html>

Very simple!, regularly with spring security, we submit the form to /j_spring_security_check but we have different situation here, we have a command button which send POST request to the same URL of the page.

2 solutions here, I'll take about one of them (as appears in Macro-blog link above) which is using a reference for the authenticationManager from the bean action method:

first, you need to expose the authenticationManager in the security context configuration file:


    <authentication-manager alias="authenticationManager">
        <authentication-provider>
            <user-service>
                <user name="admin" password="admin" authorities="ROLE_ADMIN" />
            </user-service>
        </authentication-provider>
    </authentication-manager>

Note the use of "alias" attribute.

Then in you JSF Managed bean, you can inject it and use it as the following:

@Inject
private AuthenticationManager authenticationManager;

@Setter
@Getter
private String username;

@Setter
@Getter
private String password;

public LoginBean() {
}

public String login() {
    try {
        Authentication authentication = authenticationManager
                .authenticate(new UsernamePasswordAuthenticationToken(
                        this.username, this.password));

        SecurityContextHolder.getContext()
                .setAuthentication(authentication);

    } catch (AuthenticationException ex) {
        log.equals(ex.getMessage());
        Util.addMessage("Login Failed: " + ex.getMessage());
        return "";
    }

    return Util.getSavedUrl() + "?faces-redirect=true";
}

The code above is pretty clear, If fail (AuthenticationExcpetion thrown, show error message), else redirect to some URL.

The point here is some URL is critical, because if the user was trying to access resource "A", then spring security asked him to login first, then after login he should access resource "A" itself not a welcome screen.

This handled by spring security, but in our case, we need to ask Spring-security explicity to give us the "SavedURL" from the session. so the implmenetation of Util.getSavedUrl() is below:

public static String getSavedUrl() {
    HttpServletRequest request = ((HttpServletRequest) FacesContext
            .getCurrentInstance().getExternalContext().getRequest());

    SavedRequest savedRequest = new HttpSessionRequestCache().getRequest(
            request, (HttpServletResponse) FacesContext
                    .getCurrentInstance().getExternalContext()
                    .getResponse());

    if (savedRequest != null) {
        try {
            URL url = new URL(savedRequest.getRedirectUrl());
            return url.getFile().substring(
                    request.getContextPath().length());
        } catch (Exception e) {
            log.error(e.getMessage() + " Using default URL");
        }
    }
    return "admin/index.xhtml?faces-redirect=true"; // default page!
}

And that's all for the first point.

Point #2 Handle HTTP error codes for Ajax requests:

JSF (and jsf based frameworks) uses Ajax in many cases,  the PrimeFaces autocomplete is a good example.

Originally with regular HTTP requests (non-Ajax), when the user try to access a resource after session expired, spring security will send error code 302 to the browser, when browser sees the response code, he will do the redirect the Login page.


But in case of Ajax requests, the ajax client should handle this on his own.

In case of JSF, (I am not the JSF expert Guy :D ) JSF uses some internal protocol sending XML between the server and the client, and this XML is well defined in matter if the server wants the client to do redirect, the server doesn't send 302 for the client, instead, he sends a response like:

<?xml version="1.0" encoding="UTF-8"?>
<partial-response>
    <redirect url="URL to redirect to"></redirect>
</partial-response>

So, when the ajax caller (who send the JSF request), see this response, he will do redirect immediately.


So, to integrate this with Spring security we need to tell it override the cod that sends the response code and add the above xml payload just in case of Ajax requests.

To do this Spring security provide a redirect strategy (org.springframework.security.web.RedirectStrategy) that you can extends and hook the spring security at some points.

So, here's a sample implementation:


package testing.ss;

import java.io.IOException;

import javax.servlet.http.HttpServletRequest;
import javax.servlet.http.HttpServletResponse;

import org.apache.commons.logging.Log;
import org.apache.commons.logging.LogFactory;
import org.springframework.security.web.RedirectStrategy;
import org.springframework.security.web.util.UrlUtils;

/**
 * Based on code from DefaultDirectStrategy and
 * https://gist.github.com/banterCZ/5160269
 * 
 * @author mhewedy
 *
 */
public class JsfRedirectStrategy implements RedirectStrategy {

    private static final String FACES_REQUEST_HEADER = "faces-request";

    protected final Log logger = LogFactory.getLog(getClass());

    private boolean contextRelative;

    /**
     * Redirects the response to the supplied URL.
     * <p>
     * If <tt>contextRelative</tt> is set, the redirect value will be the value
     * after the request context path. Note that this will result in the loss of
     * protocol information (HTTP or HTTPS), so will cause problems if a
     * redirect is being performed to change to HTTPS, for example.
     */
    public void sendRedirect(HttpServletRequest request,
            HttpServletResponse response, String url) throws IOException {
        String redirectUrl = calculateRedirectUrl(request.getContextPath(), url);
        redirectUrl = response.encodeRedirectURL(redirectUrl);

        boolean ajaxRedirect = "partial/ajax".equals(request
                .getHeader(FACES_REQUEST_HEADER));
        if (ajaxRedirect) {

            String ajaxRedirectXml = createAjaxRedirectXml(redirectUrl);
            logger.debug("Ajax partial response to redirect: "
                    + ajaxRedirectXml);

            response.setContentType("text/xml");
            response.getWriter().write(ajaxRedirectXml);
        } else {
            logger.debug("Non-ajax redirecting to '" + redirectUrl + "'");
            response.sendRedirect(redirectUrl);
        }
    }

    private String calculateRedirectUrl(String contextPath, String url) {
        if (!UrlUtils.isAbsoluteUrl(url)) {
            if (contextRelative) {
                return url;
            } else {
                return contextPath + url;
            }
        }

        // Full URL, including http(s)://

        if (!contextRelative) {
            return url;
        }

        // Calculate the relative URL from the fully qualified URL, minus the
        // last
        // occurrence of the scheme and base context.
        url = url.substring(url.lastIndexOf("://") + 3); // strip off scheme
        url = url.substring(url.indexOf(contextPath) + contextPath.length());

        if (url.length() > 1 && url.charAt(0) == '/') {
            url = url.substring(1);
        }

        return url;
    }

    /**
     * If <tt>true</tt>, causes any redirection URLs to be calculated minus the
     * protocol and context path (defaults to <tt>false</tt>).
     */
    public void setContextRelative(boolean useRelativeContext) {
        this.contextRelative = useRelativeContext;
    }

    // from https://gist.github.com/banterCZ/5160269
    private String createAjaxRedirectXml(String redirectUrl) {
        return new StringBuilder()
                .append("<?xml version=\"1.0\" encoding=\"UTF-8\"?>")
                .append("<partial-response><redirect url=\"")
                .append(redirectUrl)
                .append("\"></redirect></partial-response>").toString();
    }

}


Then you have to hock the LoginUrlAuthenticationEntryPoint, but because the RedirectStrategy is a final variable, you have to extend it like this:

package testing.ss;

import java.io.IOException;

import javax.servlet.RequestDispatcher;
import javax.servlet.ServletException;
import javax.servlet.http.HttpServletRequest;
import javax.servlet.http.HttpServletResponse;

import org.apache.commons.logging.Log;
import org.apache.commons.logging.LogFactory;
import org.springframework.security.core.AuthenticationException;
import org.springframework.security.web.RedirectStrategy;
import org.springframework.security.web.authentication.LoginUrlAuthenticationEntryPoint;

/**
 * Based on code from LoginUrlAuthenticationEntryPoint
 * 
 * @author mhewedy
 *
 */
// see http://forum.spring.io/forum/spring-projects/security/88829-is-it-possible-to-change-spring-security-3-redirects-from-full-urls-to-relative-urls
@SuppressWarnings("deprecation")
public class JsfLoginUrlAuthenticationEntryPoint extends
        LoginUrlAuthenticationEntryPoint {

    Log log = LogFactory.getLog(getClass());

    private RedirectStrategy redirectStrategy;

    public void setRedirectStrategy(RedirectStrategy redirectStrategy) {
        this.redirectStrategy = redirectStrategy;
    }

    @Override
    public void commence(HttpServletRequest request,
            HttpServletResponse response, AuthenticationException authException)
            throws IOException, ServletException {

        String redirectUrl = null;

        if (isUseForward()) {

            if (isForceHttps() && "http".equals(request.getScheme())) {
                // First redirect the current request to HTTPS.
                // When that request is received, the forward to the login page
                // will be used.
                redirectUrl = buildHttpsRedirectUrlForRequest(request);
            }

            if (redirectUrl == null) {
                String loginForm = determineUrlToUseForThisRequest(request,
                        response, authException);

                log.debug("Server side forward to: " + loginForm);

                RequestDispatcher dispatcher = request
                        .getRequestDispatcher(loginForm);

                dispatcher.forward(request, response);

                return;
            }
        } else {
            // redirect to login page. Use https if forceHttps true

            redirectUrl = buildRedirectUrlToLoginPage(request, response,
                    authException);
        }
        redirectStrategy.sendRedirect(request, response, redirectUrl);
    }

}


Then go back and configure http tag to reference the Entry Point:

<http auto-config="true" use-expressions="true" entry-point-ref="authenticationEntryPoint">
    .....
</http>

<beans:bean id="authenticationEntryPoint"
    class="testing.ss.JsfLoginUrlAuthenticationEntryPoint" p:loginFormUrl="/login.xhtml"
    p:redirectStrategy-ref="redirectStrategy" />
    
<beans:bean id="redirectStrategy" class="testing.ss.JsfRedirectStrategy" />

And that's all.

The complete source code on github.